Spanning trees with many leaves: lower bounds in terms of the number of vertices of degree 1, 3 and at least 4
From MaRDI portal
Publication:744554
DOI10.1007/S10958-014-1692-7zbMATH Open1298.05184arXiv1205.5163OpenAlexW3104321172MaRDI QIDQ744554FDOQ744554
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 vertices of degree~1 and 3 and vertices of degree at least~4 has a spanning tree with at least leaves. We present infinite series of graphs showing that our bound is tight.
Full work available at URL: https://arxiv.org/abs/1205.5163
Recommendations
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
- 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 (26)
- Degree conditions for graphs to have spanning trees with few branch vertices and leaves
- Improved bounds for spanning trees with many leaves
- On a spanning \(k\)-tree in which specified vertices have degree less than \(k\)
- Spanning trees with bounded degrees and leaves
- Spanning trees with a bounded number of leaves
- Some results on spanning trees
- Spanning trees with many leaves
- Spanning trees: A survey
- Title not available (Why is that?)
- Constructing a spanning tree with many leaves
- Spanning trees with large number of end vertices
- 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 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
- Characterizing spanning trees via the size or the spectral radius of graphs
- Bounds of the number of leaves of spanning trees
- Spanning Trees with Many Leaves in Graphs With Minimum Degree Three
- Spanning trees with few leaves
- Spanning trees with constraints on the leaf degree
- Spanning trees with few non-leaves
- Arbres avec un nombre maximum de sommets pendants
- Connected domination
- 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)
