张明瑜

(山西大同大学数学与计算机科学学院，山西大同037009)

树与余树的断裂度的关系

张明瑜

(山西大同大学数学与计算机科学学院，山西大同037009)

断裂度是图的哈密尔顿性和容错性的一个有效度量。给出了树和它的余树的断裂度的和与积的取值范围。

断裂度；树；余树

设G是一个图，它的顶点集和边集分别表示为V(G)和E(G)。不包含圈的图称为无圈图，连通的无圈图称为树。树T的补图称为它的余树，记为。用Δ(G)和δ(G)分别表示G的顶点的最大度和最小度。Kn表示n阶完全图，K1,n-1表示一部顶点数为1，另一部顶点数为n-1的完全二部图。表示整数a除以整数b的余数。和分别表示取上整和取下整。文中其它未给出的定义见文献[1]。

定义1对连通图G，设S⊂V(G)。当G不是完全图时，若G-S不连通，则称S是G的点断集；当G=Kn时，Kn的任何n-1个点组成的集合也称为G的点断集。

定义2[2]设G是一个连通图。图G的断裂度定义为，若S*是G的一个点断集，满足，则称S*为G的一个断裂度集。

定义3[3]设n(n≥2)，Δ是两个给定的整数，T[n,Δ]表示顶点数为n最大度为Δ的所有树组成的集合。

引理1[4]设n,Δ(n≥ 2,Δ≥ 1)是两个使得T[n,Δ]≠0的整数。那么

引理2若图G连通且G不是完全图，则sc(G)≥ 2-δ(G)。

引理3设T是一棵n(n≥4)阶树，为树T的余树，则连通且

引理4设T是一棵n(≥4)阶树，是树T的余树，则

引理5[3]具有n个顶点且最大度数为Δ的树可能具有的最小断裂度为

定理1设T是一棵n阶树，是树T的余树，则有

证明由引理1，2和引理3结论（1)显然。下面证明结论（2）。由和连通有n≥ Δ+2。

[1]BONDY J A,MURTY U S R.Graph Theory[M].New York：Springer,2007.

[2]王世英，杨玉星，林上为，等.图的孤立断裂度[J].数学学报,2011,54(5)：861-874.

[3]许进.系统的核与核度理论及应用[M].西安：西安交通大学出版社，1993.

[4]张明瑜，王世英.树的断裂度的紧上届[J].太原师范学院学报（自然科学版）,2008,7(3)：1-4.

Relation of the Scattering Number of the Trees and Its Complement Trees

ZHANG Ming-yu
(School of Mathematics and Computer Science,Shanxi Datong University,Datong Shanxi，037009）

The scattering number is an effective measure of the hamiltonicity and vulnerability of graphs.In this paper,we present the rang of the sum and product of the scattering number for tree and its complemen treet.

scattering number;trees;complement tree

O157.5

A

1674-0874(2017)06-0014-02

2017-08-26

张明瑜（1983-）,女，山西应县人，硕士，实验师，研究方向：图论及其应用。

〔责任编辑 高海〕