Displaying similar documents to “On Two Generalized Connectivities of Graphs”

The leafage of a chordal graph

In-Jen Lin, Terry A. McKee, Douglas B. West (1998)

Discussiones Mathematicae Graph Theory

Similarity:

The leafage l(G) of a chordal graph G is the minimum number of leaves of a tree in which G has an intersection representation by subtrees. We obtain upper and lower bounds on l(G) and compute it on special classes. The maximum of l(G) on n-vertex graphs is n - lg n - 1/2 lg lg n + O(1). The proper leafage l*(G) is the minimum number of leaves when no subtree may contain another; we obtain upper and lower bounds on l*(G). Leafage equals proper leafage on claw-free chordal graphs. We use...

Bounding neighbor-connectivity of Abelian Cayley graphs

Lynne L. Doty (2011)

Discussiones Mathematicae Graph Theory

Similarity:

For the notion of neighbor-connectivity in graphs whenever a vertex is subverted the entire closed neighborhood of the vertex is deleted from the graph. The minimum number of vertices whose subversion results in an empty, complete, or disconnected subgraph is called the neighbor-connectivity of the graph. Gunther, Hartnell, and Nowakowski have shown that for any graph, neighbor-connectivity is bounded above by κ. Doty has sharpened that bound in abelian Cayley graphs to approximately...

Note: Sharp Upper and Lower Bounds on the Number of Spanning Trees in Cartesian Product of Graphs

Jernej Azarija (2013)

Discussiones Mathematicae Graph Theory

Similarity:

Let G1 and G2 be simple graphs and let n1 = |V (G1)|, m1 = |E(G1)|, n2 = |V (G2)| and m2 = |E(G2)|. In this paper we derive sharp upper and lower bounds for the number of spanning trees τ in the Cartesian product G1 □G2 of G1 and G2. We show that: [...] and [...] . We also characterize the graphs for which equality holds. As a by-product we derive a formula for the number of spanning trees in Kn1 □Kn2 which turns out to be [...] .

Tree-Like Partial Hamming Graphs

Tanja Gologranc (2014)

Discussiones Mathematicae Graph Theory

Similarity:

Tree-like partial cubes were introduced in [B. Brešar, W. Imrich, S. Klavžar, Tree-like isometric subgraphs of hypercubes, Discuss. Math. Graph Theory, 23 (2003), 227-240] as a generalization of median graphs. We present some incorrectnesses from that article. In particular we point to a gap in the proof of the theorem about the dismantlability of the cube graph of a tree-like partial cube and give a new proof of that result, which holds also for a bigger class of graphs, so called tree-like...