Connected Domination and Spanning Trees with Many Leaves

DOI10.1137/S0895480199353780zbMath0941.05045MaRDI QIDQ4490780

Douglas B. West, Raphael Yuster, Yair Caro

Publication date: 20 July 2000

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

connectivitydominationspanning trees

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40)

Related Items

The 3-rainbow index and connected dominating sets, Bounds on the leaf number in graphs of girth 4 or 5, Computational approaches for zero forcing and related problems, Note on the upper bound of the rainbow index of a graph, Bounds on domination parameters in graphs: a brief survey, Lower bounds on the number of leaves in spanning trees, Traceability of connected domination critical graphs, Further results on the total monochromatic connectivity of graphs, Some results on spanning trees, Bounds of the number of leaves of spanning trees in graphs without triangles, Bounds of the number of leaves of spanning trees, Spanning trees with few non-leaves, Improved bounds for spanning trees with many leaves, Connected domination in random graphs, Radius, leaf number, connected domination number and minimum degree, Spanning Trees and Domination in Hypercubes, Domination parameters of a graph and its complement, Minimum Degree and Dominating Paths, Connected power domination in graphs, 2-connected graphs with small 2-connected dominating sets., On the Structure of Graphs Vertex Critical with Respect to Connected Domination, Some upper bounds for the 3-proper index of graphs, Bounds on the connected domination number of a graph, Spanning Trees with Many Leaves in Regular Bipartite Graphs, Spanning trees: A survey, Connected domination number of a graph and its complement, \(k\)-domination and \(k\)-independence in graphs: A survey, Upper bounds on the \(k\)-forcing number of a graph, Matching properties in connected domination critical graphs, Partial domination - the isolation number of a graph, Some extremal results on the colorful monochromatic vertex-connectivity of a graph, Constructing a spanning tree with many leaves, Complexity and computation of connected zero forcing, 2-edge connected dominating sets and 2-connected dominating sets of a graph, Spanning trees with many leaves: new lower bounds in terms of the number of vertices of degree 3 and at least 4, Spanning trees with many leaves: lower bounds in terms of the number of vertices of degree 1, 3 and at least 4, Connected Domination, ANOTHER LOOK AT k-DOMINATION IN GRAPHS, Connected domination of regular graphs, A note on connected domination number and leaf number, Average degree conditions forcing a minor