Spanning trees homeomorphic to a small tree

作者：Saito Akira^*; Sano Kazuki

来源：Discrete Mathematics, 2016, 339(2): 677-681.

DOI：10.1016/j.disc.2015.10.004

• Spanning tree
• Subdivision
• Homeomorphic
• Hamiltonian path

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 1(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.

• 出版日期2016-2-6