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

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

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

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

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

和

設G的頂點集V（G）為｛v1，v2，…，vn｝且不失一般性，設U＝｛v1，v2，…，vα（G）｝是G的一個最大獨立集.

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

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

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

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

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

證明 設S＊是G的孤立斷裂度集.由定理2，有ω（G－S＊）≤｜S＊｜.因為i（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 設n（≥8）和r為兩個給定的正整數(shù)使得－（n－6）≤r≤－4.那么存在n階互補的哈密頓圖H和，使得isc（H）＋isc）＝r.

證明 當n為偶數(shù)時，由引理12知存在n階互補的哈密頓圖H和，使得isc（H）＋isc（）是｛－（n－6），…，－4，－3｝中任意一個數(shù).當n為奇數(shù)時，由引理12知存在n階互補的哈密頓圖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ù)學學報，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］ 王世英，張東艷.圖與補圖斷裂度的關(guān)系［J］.晉中師專學報，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

國家自然科學基金（61070229）；教育部博士點基金（博導類）（20111401110005）

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