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

DOI10.1007/S10958-014-1692-7MaRDI QIDQ744554zbMATH 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/1205.5163

zbMATH Keywords

spanning tree

Mathematics Subject Classification ID

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

Abstract: We prove that every connected graph with $s$ vertices of degree~1 and 3 and $t$ vertices of degree at least~4 has a spanning tree with at least $1over3t+1over4s+3over2$ leaves. We present infinite series of graphs showing that our bound is tight.

Recommendations

• Spanning trees with many leaves: new lower bounds in terms of the number of vertices of degree 3 and at least 4
• Bounds of the number of leaves of spanning trees
• Spanning Trees with Many Leaves
• Spanning trees with many leaves
• Spanning trees in graphs of minimum degree 4 or 5

Cites work

• 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

(26)

• Improved bounds for spanning trees with many leaves
• Degree conditions for graphs to have spanning trees with few branch vertices and leaves
• Spanning trees with bounded degrees and leaves
• On a spanning \(k\)-tree in which specified vertices have degree less than \(k\)
• Some results on spanning trees
• Spanning trees with a bounded number of leaves
• Spanning trees with many leaves
• Spanning trees: A survey
• scientific article; zbMATH DE number 2058113 (Why is no real title available?)
• Constructing a spanning tree with many leaves
• 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 large number of end vertices
• Spanning trees with leaves bounded by independence number
• Bounds of the number of leaves of spanning trees in graphs without triangles
• 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
• Characterizing spanning trees via the size or the spectral radius of graphs
• Spanning trees with few leaves
• Spanning trees with constraints on the leaf degree
• Arbres avec un nombre maximum de sommets pendants
• Connected domination
• Spanning trees with few non-leaves
• A bound on the number of leaves in a spanning tree of a connected graph of minimum degree 6
• Vulnerability bounds on the number of spanning tree leaves

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

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