Back to Search
Start Over
Spanning trees homeomorphic to a small tree.
- Source :
-
Discrete Mathematics . Feb2016, Vol. 339 Issue 2, p677-681. 5p. - Publication Year :
- 2016
-
Abstract
- A classical result of Ore states that if a graph G of order n satisfies deg G x + deg G y ≥ n − 1 for every pair of nonadjacent vertices x and y of G , then G contains a hamiltonian path. In this note, we interpret a hamiltonian path as a spanning tree which is a subdivision of K 2 and extend Ore’s result to a sufficient condition for the existence of a spanning tree which is a subdivision of a tree of a bounded order. We prove that for a positive integer k , if a connected graph G satisfies deg G x + deg G y ≥ n − k for every pair of nonadjacent vertices x and y of G , then G contains a spanning tree which is a subdivision of a tree of order at most k + 2 . We also discuss the sharpness of the result. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 339
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 111440698
- Full Text :
- https://doi.org/10.1016/j.disc.2015.10.004