樹與余樹的斷裂度的關(guān)系

張明瑜

(山西大同大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，山西大同037009)

樹與余樹的斷裂度的關(guān)系

張明瑜

(山西大同大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，山西大同037009)

斷裂度是圖的哈密爾頓性和容錯(cuò)性的一個(gè)有效度量。給出了樹和它的余樹的斷裂度的和與積的取值范圍。

斷裂度；樹；余樹

設(shè)G是一個(gè)圖，它的頂點(diǎn)集和邊集分別表示為V(G)和E(G)。不包含圈的圖稱為無圈圖，連通的無圈圖稱為樹。樹T的補(bǔ)圖稱為它的余樹，記為。用Δ(G)和δ(G)分別表示G的頂點(diǎn)的最大度和最小度。Kn表示n階完全圖，K1,n-1表示一部頂點(diǎn)數(shù)為1，另一部頂點(diǎn)數(shù)為n-1的完全二部圖。表示整數(shù)a除以整數(shù)b的余數(shù)。和分別表示取上整和取下整。文中其它未給出的定義見文獻(xiàn)[1]。

定義1對(duì)連通圖G，設(shè)S?V(G)。當(dāng)G不是完全圖時(shí)，若G-S不連通，則稱S是G的點(diǎn)斷集；當(dāng)G=Kn時(shí)，Kn的任何n-1個(gè)點(diǎn)組成的集合也稱為G的點(diǎn)斷集。

定義2[2]設(shè)G是一個(gè)連通圖。圖G的斷裂度定義為，若S*是G的一個(gè)點(diǎn)斷集，滿足，則稱S*為G的一個(gè)斷裂度集。

定義3[3]設(shè)n(n≥2)，Δ是兩個(gè)給定的整數(shù)，T[n,Δ]表示頂點(diǎn)數(shù)為n最大度為Δ的所有樹組成的集合。

引理1[4]設(shè)n,Δ(n≥ 2,Δ≥ 1)是兩個(gè)使得T[n,Δ]≠0的整數(shù)。那么

引理2若圖G連通且G不是完全圖，則sc(G)≥ 2-δ(G)。

引理3設(shè)T是一棵n(n≥4)階樹，為樹T的余樹，則連通且

引理4設(shè)T是一棵n(≥4)階樹，是樹T的余樹，則

引理5[3]具有n個(gè)頂點(diǎn)且最大度數(shù)為Δ的樹可能具有的最小斷裂度為

定理1設(shè)T是一棵n階樹，是樹T的余樹，則有

證明由引理1，2和引理3結(jié)論（1)顯然。下面證明結(jié)論（2）。由和連通有n≥ Δ+2。

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

[2]王世英，楊玉星，林上為，等.圖的孤立斷裂度[J].數(shù)學(xué)學(xué)報(bào),2011,54(5)：861-874.

[3]許進(jìn).系統(tǒng)的核與核度理論及應(yīng)用[M].西安：西安交通大學(xué)出版社，1993.

[4]張明瑜，王世英.樹的斷裂度的緊上屆[J].太原師范學(xué)院學(xué)報(bào)（自然科學(xué)版）,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-）,女，山西應(yīng)縣人，碩士，實(shí)驗(yàn)師，研究方向：圖論及其應(yīng)用。

〔責(zé)任編輯 高?！?/p>