＊圖與補(bǔ)圖孤立斷裂度的關(guān)系

王世英，王牟江山，馮凱，林上為，張明瑜

（1.山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山西 太原 030006；2.中國科學(xué)院 研究生院，北京 100049；3.山西大學(xué) 計算機(jī)與信息技術(shù)學(xué)院，山西 太原 030006）

＊圖與補(bǔ)圖孤立斷裂度的關(guān)系

王世英1，王牟江山2，馮凱3，林上為1，張明瑜1

（1.山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山西 太原 030006；2.中國科學(xué)院 研究生院，北京 100049；3.山西大學(xué) 計算機(jī)與信息技術(shù)學(xué)院，山西 太原 030006）

連通圖G的孤立斷裂度isc（G）＝max｛i（G－S）－｜S｜∶S∈C（G）｝，其中i（G－S）是G－S中的孤立點(diǎn)數(shù)，C（G）是G的點(diǎn)割集.文章研究了圖與補(bǔ)圖孤立斷裂度的關(guān)系.

網(wǎng)絡(luò)；可靠性；孤立斷裂度

0 引言

本文僅考慮簡單圖.設(shè)圖G＝（V（G），E（G）），其中V（G）和E（G）分別為圖G的頂點(diǎn)集和邊集.若｜V（G）｜＝1，則稱G為平凡圖.設(shè)S?V（G）.當(dāng)G是完全圖時，若G－S是平凡圖，稱S是G的一個點(diǎn)割；當(dāng)G是非完全連通圖時，若G－S是不連通的，則稱S是G的一個點(diǎn)割；G的連通度κ（G）為G的一個最小點(diǎn)割的頂點(diǎn)數(shù).G的點(diǎn)割集C（G）＝｛S∶S是G的一個點(diǎn)割｝.G的分支數(shù)，奇分支數(shù)和孤立頂點(diǎn)數(shù)分別用ω（G），ω0（G）和i（G）表示.G的虧度def（G）是指G中未被G的一個最大匹配飽和的頂點(diǎn)數(shù).下面是匹配理論中著名的 Tutte定理［1］.

定理1（Tutte定理［1］） 一個圖G有完美匹配當(dāng)且僅當(dāng)對所有的S?V（G），有ω0（G－S）≤｜S｜成立.

1958年，Berge在Tutte定理的基礎(chǔ)上給出了圖G的一個最大匹配的精確刻畫.特別的，他證明了def（G）＝max｛ω0（G－S）－｜S｜∶S?V（G）｝.此后，虧度這一參數(shù)得到許多學(xué)者的關(guān)注［2－5］.下面給出另一個著名的定理.

定理2［1］設(shè)S為哈密頓圖G的一個頂點(diǎn)集合.則ω（G－S）≤｜S｜.

受該定理的啟發(fā)，Jung［6］引進(jìn)斷裂度這一新概念來對圖的哈密頓性進(jìn)行討論.

定義1［6］設(shè)G為一個連通圖.圖G的斷裂度sc（G）＝max｛ω（G－S）－｜S｜∶S∈C（G）｝.

斷裂度源于分?jǐn)?shù)因子理論，近年來，它被普遍認(rèn)為是度量圖的可靠性的有效參數(shù)之一［7－11］.分?jǐn)?shù)因子理論［12－13］被廣泛應(yīng)用在網(wǎng)絡(luò)設(shè)計，組合拓?fù)浜蜎Q策鏈等很多領(lǐng)域.一個分?jǐn)?shù)1－因子是指一個為圖G的每條邊指派一個區(qū)間［0，1］上分?jǐn)?shù)的函數(shù)h，使得對每個頂點(diǎn)x有 ∑e∈Ex h（e）＝1成立，其中Ex＝｛e∶e＝xy∈E（G）｝.下面給出具有分?jǐn)?shù)1－因子圖的一個刻畫.

定理3［12］一個圖G有分?jǐn)?shù)1－因子當(dāng)且僅當(dāng)對任何S?V（G）有i（G－S）≤｜S｜成立.

受定理3的啟發(fā)，王世英等在文［14］中引進(jìn)孤立斷裂度這一新概念對圖的穩(wěn)定性進(jìn)行討論.

定義2［14］設(shè)G是一個連通圖.圖G的孤立斷裂度isc（G）＝max｛i（G－S）－｜S｜∶S∈C（G）｝.

設(shè)S＊是圖G的一個點(diǎn)割，若i（G－S＊）－｜S＊｜＝isc（G），則稱S＊為一個孤立斷裂度集.

一個處理器互連網(wǎng)絡(luò)或通訊網(wǎng)絡(luò)通常用一個圖G＝（V，E）來表示，其中V中每個頂點(diǎn)對應(yīng)一個處理器或一個通訊器件，E中每條邊對應(yīng)一對處理器或一對通訊器件之間的一條直接通訊線路.在設(shè)計這些網(wǎng)絡(luò)時，可靠性是一個非常重要的因素［15］.由于孤立頂點(diǎn)同其他頂點(diǎn)無法通訊聯(lián)系，所以我們期望故障網(wǎng)絡(luò)具有盡可能少的孤立頂點(diǎn).對G的一個點(diǎn)割S，從G中移除S的難度可以用｜S｜來度量，由S的移除帶來的徹底毀壞程度可用i（G－S）來度量.因此，孤立斷裂度是一個合理、合適的網(wǎng)絡(luò)可靠性參數(shù).本文對圖與補(bǔ)圖孤立斷裂度的關(guān)系進(jìn)行研究.下面我們介紹將用到一些基本概念和術(shù)語.

V（G）的一個子集S被稱為一個獨(dú)立集若S中任意兩個頂點(diǎn)在G中都不相鄰.G的最大獨(dú)立集的頂點(diǎn)數(shù)稱為G的獨(dú)立數(shù)，記為α（G）.V（G）的一個子集K使得G中每條邊至少有一個端點(diǎn)在K中被稱為G的一個覆蓋.G的最小覆蓋的頂點(diǎn)數(shù)稱為G的覆蓋數(shù)，記為β（G）.設(shè)X是V（G）的一個非空子集.G的由X導(dǎo)出的子圖記為G［X］.G［V（G）－X］簡記為G－X.若X＝｛v｝，則G－｛v｝簡記為G－v.其它未給出的定義參見［1］.

1 圖與補(bǔ)圖孤立斷裂度的關(guān)系

和

設(shè)G的頂點(diǎn)集V（G）為｛v1，v2，…，vn｝且不失一般性，設(shè)U＝｛v1，v2，…，vα（G）｝是G的一個最大獨(dú)立集.

若i（G－S＊）＝3，｜S＊｜＝2，設(shè)S＊＝｛x1，x2｝，點(diǎn)x3、x4和x5為G－S＊中的孤立點(diǎn).注意到｛x3，x4，x5｝中必有一個點(diǎn)在G［U2］中.又由于G［U2］是完全圖，而｛x3，x4，x5｝是孤立點(diǎn)集，故｛x3，x4，x5｝中恰有一個點(diǎn)在G［U2］中.因此，不妨設(shè)為x3∈U2且｛x4，x5｝＝｛v1，v2｝.注意到G［U2］是G中的（n－2）團(tuán)，故若V（G）＼（S＊∪｛x3，x4，x5｝）中還存在其它的點(diǎn)x＊，則x＊與x3在G－S＊中必相鄰，這與x3為G－S＊中的孤立點(diǎn)矛盾.因此，n＝5.這時x3＝v3.否則不妨設(shè)x3＝v4，這時｛x1，x2｝＝｛v3，v5｝.不妨設(shè)x1＝v3，x2＝v5，由于｛v1，v2，v3｝是G的獨(dú)立集，故v5與v1，v2均相鄰.由于｛v3，v4，v5｝＝U2，故G［U2］是一個完全圖.因此，d G（v5）＝4，即dˉG（v5）＝0，矛盾.這時｛x1，x2｝＝｛v4，v5｝.此時G［｛v3，v4，v5｝］是完全圖，G［｛v1，v2，v3｝］是空圖且v1與｛v4，v5｝中至少一點(diǎn)相鄰，v2與｛v4，v5｝中至少一點(diǎn)相鄰.若v1，v2都與v4相鄰，則在ˉG中v4是孤立點(diǎn)，矛盾.同理，v1，v2不能都與v5相鄰.因此，不失一般性可設(shè)v1只與v4相鄰，v2只與v5相鄰，這說明G?G5.證畢.

以下兩個引理的結(jié)果是顯然的故未給出證明.

2 互補(bǔ)的哈密頓圖的孤立斷裂度的關(guān)系

引理10［1］一個簡單圖是哈密頓圖當(dāng)且僅當(dāng)它的閉包是哈密頓圖.

引理11 若G是哈密頓圖，則G的孤立斷裂度isc（G）≤0.

證明 設(shè)S＊是G的孤立斷裂度集.由定理2，有ω（G－S＊）≤｜S＊｜.因?yàn)閕（G－S＊）≤ω（G－S＊），所以isc（G）＝i（G－S＊）－｜S＊｜≤ω（G－S＊）－｜S＊｜≤0.證畢.

由引理10容易得到下面的引理.

引理12 對任意給定的正整數(shù)n（≥8）和k（1≤k≤n－7），構(gòu)造n階圖H如下：V（H）＝｛v1，v2，…，vn｝，E（H）＝E（Kn）＼（E1∪E2），其中E1＝｛viv i＋1∶i＝1，2，…，n，1＋i是模n加法｝，E2＝｛v1vi∶i＝3，…，k＋2｝.則

證明 由引理11可得isc（H）＋isc（）≤0.由定理5有isc（H）＋isc（）≥－（n－3）.證畢.

定理9 設(shè)n（≥8）和r為兩個給定的正整數(shù)使得－（n－6）≤r≤－4.那么存在n階互補(bǔ)的哈密頓圖H和，使得isc（H）＋isc）＝r.

證明 當(dāng)n為偶數(shù)時，由引理12知存在n階互補(bǔ)的哈密頓圖H和，使得isc（H）＋isc（）是｛－（n－6），…，－4，－3｝中任意一個數(shù).當(dāng)n為奇數(shù)時，由引理12知存在n階互補(bǔ)的哈密頓圖H和ˉH，使得isc（H）＋isc（ˉH）是｛－（n－5），－（n－6），…，－4｝中任意一個數(shù).綜上得證.

［1］ Bondy J A，Murty U S R.Graph Theory［M］.New York：Springer，2007.

［2］ Bauer D，Broersma H J，Morgana A，etal.Tutte Sets in Graphs I：maximal Tutte sets and D－graphs［J］.JournalofGraph Theory，2007，55（4）：343－358.

［3］ Bauer D，Broersma H J，Kahl N，etal.Tutte Sets in Graphs II：The Complexity of Finding Maximum Tutte Sets［J］.DiscreteAppliedMathematics，2007，155（15）：1336－1343.

［4］ Busch A，F(xiàn)errara M，Kahl N.Generalizing D－graphs［J］.DiscreteAppliedMathematics，2007，155（18）：2487－2495.

［5］ Traldi L.Parallel Connections and Coloured Tutte Polynomials［J］.DiscreteMathematics，2005，290（2－3）：291－299.

［6］ Jung H A.On a Class of Posets and the Corresponding Comparability Graphs［J］.JournalofCombinatorialTheorySeriesB，1978，24（2）：125－133.

［7］ Giakoumakis V，Roussel F，Thuillier H.Scattering Number and Modular Decomposition［J］.DiscreteMathematics，1997，165－166（15）：321－342.

［8］ Kirlangic A.A Measure of Graph Vulnerability：Scattering Number［J］.InternationalJournalofMathematicsandMathematicalSciences，2002，30（1）：1－8.

［9］ Li F W，Li X L.The Neighbour－scattering Number can Be Computed in Polynomial time for Interval Graphs［J］.ComputersandMathematicswithApplications，2007，54（5）：679－686.

［10］ Kratsch D，Kloks T，Müller H.Measuring the Vulnerability for Classes of Intersection Graphs［J］.DiscreteApplied Mathematics，1997，77（3）：259－270.

［11］ Zhang S G，Wang Z G.Scattering Number in Graphs［J］.Networks，2001，37（2）：102－106.

［12］ Edward R，Scheinerman E，Ullman D H.Fractional Graph Theory：A Rational Approach to the Theory of Graphs［M］.New York：John Wiley and Sons Inc，1997.

［13］ Liu Y，Liu G Z.The Fractional Matching Numbers of Graphs［J］.Networks，2002，40（4）：228－231.

［14］ 王世英，楊玉星，林上為，等.圖的孤立斷裂度［J］.數(shù)學(xué)學(xué)報，2011，54（5）：861－874.

［15］ Bermond J C，Homobono N，Peyrat C.Large Fault－tolerant Interconnection Networks［J］.GraphsandCombinatorics，1989，5（1）：107－123.

［16］ 王世英，張東艷.圖與補(bǔ)圖斷裂度的關(guān)系［J］.晉中師專學(xué)報，1991，1：37－41.

［17］ Chartrand G，Schuster S.On the Independence Number of Complementary graphs［J］.TransactionsoftheNewYorkA－cademyofScienceⅡ，1974，36（3）：247－281.

Relation of the Isolated Scatting Number of a Graph and Its Complement Graph

WANG Shi－ying1，WANGMU Jiang－shan2，F(xiàn)ENG Kai3，LIN Shang－wei1，ZHANG Ming－yu1
（1.SchoolofMathematicalScience，ShanxiUniversity，Taiyuan030006，China；2.GraduateUniversityofChineseAcademyofSciences，Beijing100049，China；3.SchoolofComputerScienceandTechnology，ShanxiUniversity，Taiyuan030006，China）

The isolated scattering numberisc（G）＝max｛i（G－S）－｜S｜：S∈C（G）｝，whereGis a connected graph，i（G－S）is the number of isolated vertices ofG－SandC（G）is the set of vertex cuts ofG.In this paper，we investigate the relation of the isolated scatting number of a graph and its complement graph.

networks；vulnerability；isolated scattering number

O157.5

A

0253－2395（2012）02－0206－05＊

2011－09－27

國家自然科學(xué)基金（61070229）；教育部博士點(diǎn)基金（博導(dǎo)類）（20111401110005）

王世英（1961－），男，山西晉中人，博士，教授，主要研究領(lǐng)域?yàn)閳D論和DNA計算.