Spanning trees homeomorphic to a small tree
Spanning trees homeomorphic to a small tree
复制标题
DOI：
10.1016/j.disc.2015.10.004
复制
发表时间：
2016-02
期刊：
影响因子：
--
通讯作者：
Akira Saito;Kazuki Sano
中科院分区：
文献类型：
--
作者：
Akira Saito;Kazuki Sano
Ore 的经典结果表明，如果 n 阶图 G 对于 G 的每对不相邻顶点 x 和 y 满足 deg G x+ deg G y≥ n− 1，则 G 包含哈密顿路径。在本文中，我们将哈密顿路径解释为生成树，它是 K 2 的细分，并将 Ore 的结果扩展到生成树存在的充分条件，生成树是有界顺序树的细分。我们证明，对于正整数 k，如果连通图 G 对于 G 的每对不相邻顶点 x 和 y 满足 deg G x+ deg G y≥ n− k，则 G 包含一个生成树，它是阶数最多为 k+ 2 的树的细分。我们还讨论了结果的锐度。
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.