Spanning k-Trees of n-Connected Graphs
Spanning k-Trees of n-Connected Graphs
复制标题
DOI：
10.1007/s00373-011-1021-6
复制
发表时间：
2011-05
影响因子：
0.7
通讯作者：
M. Kano;Hiroo Kishimoto
中科院分区：
文献类型：
--
作者：
M. Kano;Hiroo Kishimoto
如果一棵树的最大度为mostk，则称其为AK-树。我们证明了下面的定理，利用这个定理可以定义n-连通图的生成k-树的闭包概念。设≥_2和n_≥_1为整数，其中|G|≥|−_1−(k_−_2)n，其中|G|表示图G的阶数，其中|G|表示图G的阶数。则G有spanningk-树当且仅IFG+uv有spanningk-树。
A tree is called ak-tree if the maximum degree is at mostk. We prove the following theorem, by which a closure concept for spanningk-trees ofn-connected graphs can be defined. Letk≥ 2 andn≥ 1 be integers, and letuandvbe a pair of nonadjacent vertices of ann-connected graphGsuch that degG(u) + degG(v) ≥ |G| − 1 − (k− 2)n, where |G| denotes the order ofG. ThenGhas a spanningk-tree if and only ifG+uvhas a spanningk-tree.