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-8zbMATH Open1298.05183arXiv1202.3082OpenAlexW2952610495MaRDI QIDQ744553FDOQ744553

Authors: D. Kharzeev 

Publication date: 25 September 2014

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

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.

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

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

zbMATH Keywords

infinite series of graphsregular graphs of degree 4

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (10)

• The number and average size of connected sets in graphs with degree constraints
• Improved bounds for spanning trees with many leaves
• Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
• Spanning trees with many leaves
• Connected Domination
• Spanning trees with many leaves in cubic graphs
• Bounds of the number of leaves of spanning trees in graphs without triangles
• Spanning Trees with Many Leaves in Graphs With Minimum Degree Three
• Spanning trees with constraints on the leaf degree
• A bound on the number of leaves in a spanning tree of a connected graph of minimum degree 6

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)