Spanning k-Trees of n-Connected Graphs

作者：Kano Mikio; Kishimoto Hiroo^*

来源：Graphs and Combinatorics, 2011, 27(3): 413-418.

DOI：10.1007/s00373-011-1021-6

• Spanning tree
• Closure for k-tree
• Spanning k-tree
• n-Connected graphs

A tree is called a k-tree if the maximum degree is at most k. We prove the following theorem, by which a closure concept for spanning k-trees of n-connected graphs can be defined. Let k a parts per thousand yen 2 and n a parts per thousand yen 1 be integers, and let u and v be a pair of nonadjacent vertices of an n-connected graph G such that deg (G) (u) + deg (G) (v) a parts per thousand yen |G| - 1 - (k - 2)n, where |G| denotes the order of G. Then G has a spanning k-tree if and only if G + uv has a spanning k-tree.

• 出版日期2011-5