包含k-树图的毁裂度条件

连通图G的一个k-树是指图G的一个最大度至多是k的生成树.对于连通图G来说,其毁裂度定义为r(G)=max{ω(G-X)-|X|-m(G-X)|X■V(G),ω(G-X)1}其中ω(G-X)和m(G-X)分别表示G-X中的分支数目和最大分支的阶数.本文结合毁裂度给出连通图G包含一个k-树的充分条件;利用图的结构性质和毁裂度的关系逐步刻画并给出图G包含一个k-树的毁裂度条件.

The condition of rupture degree for a graph has k tree

A k-tree of a connected graph G is a spanning tree with maximum degree at most k. The rupture degree for a connected graph G is defined by r(G)=max{ω(G?X)?|X|?m(G?X):X ?V (G),ω(G?X)>1}where m(G?X) andω(G?X), respectively, denote the order of the largest component and number of components in G?X. In this paper we find a necessary condition for a connected graph G has a k-tree;By the relationship between graph structure and rupture degree to determine the exist condition.