Spanning trees with many leaves: new lower bounds in terms of the number of vertices of degree 3 and at least 4

DOI10.1007/S10958-014-1691-8MaRDI QIDQ744553zbMATH OpenOpenAlexFDO

Authors D. Kharzeev

Publication date 25 September 2014

Published in Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.3082

zbMATH Keywords

infinite series of graphsregular graphs of degree 4

Mathematics Subject Classification ID

Trees (05C05) Vertex degrees (05C07) Connectivity (05C40)

Abstract: We prove, that every connected graph with $s$ vertices of degree 3 and $t$ vertices of degree at least~4 has a spanning tree with at least $2over5t+1over5s+alpha$ leaves, where $alphage8over5$. Moreover, $alphage2$ for all graphs besides three exclusions. All exclusion are regular graphs of degree~4, they are explicitly described in the paper. We present infinite series of graphs, containing only vertices of degrees~3 and~4, for which the maximal number of leaves in a spanning tree is equal for $2over5t+1over5s+2$. Therefore we prove that our bound is tight.

Recommendations

• Spanning trees with many leaves: lower bounds in terms of the number of vertices of degree 1, 3 and at least 4
• Bounds of the number of leaves of spanning trees
• Spanning Trees with Many Leaves
• Spanning Trees with Many Leaves in Graphs With Minimum Degree Three
• Constructing a spanning tree with many leaves

Cites work

• A recursive characterization of the 4-connected graphs
• Bounds of the number of leaves of spanning trees
• Connected Domination and Spanning Trees with Many Leaves
• Constructing full spanning trees for cubic graphs
• Spanning Trees with Many Leaves
• Spanning Trees with Many Leaves in Graphs With Minimum Degree Three
• Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
• Spanning trees in graphs of minimum degree 4 or 5
• Spanning trees with many leaves
• Transversal numbers of uniform hypergraphs

Cited in

(16)

• Lower bounds on the number of leaves in spanning trees
• Spanning trees with minimum number of leaves in the square graph of a tree
• Bounds of the number of leaves of spanning trees
• Spanning Trees with Many Leaves in Graphs With Minimum Degree Three
• Improved bounds for spanning trees with many leaves
• Constructing a spanning tree with many leaves
• Spanning trees with many leaves: lower bounds in terms of the number of vertices of degree 1, 3 and at least 4
• The number and average size of connected sets in graphs with degree constraints
• Spanning trees with constraints on the leaf degree
• Spanning trees with many leaves
• Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
• Bounds of the number of leaves of spanning trees in graphs without triangles
• A bound on the number of leaves in a spanning tree of a connected graph of minimum degree 6
• Connected domination
• Number of vertices of degree three in spanning 3-trees in square graphs
• Spanning trees with many leaves in cubic graphs

This page was built for publication: Spanning trees with many leaves: new lower bounds in terms of the number of vertices of degree 3 and at least 4

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q744553)