一些重要圖類的條件連通度.pdf

1、連通度和邊連通度是衡量網(wǎng)絡(luò)可靠性的一個重要參數(shù)。作為經(jīng)典連通度的推廣，人們提出了條件(邊)連通度。本文主要研究一些重要圖類的條件(邊)連通度。 第一章介紹了背景和一些基本概念。第二章主要研究Bi-Cayley圖的超邊連通性和最優(yōu)超邊連通性。設(shè)G是一個有限群，S(可以含有單位元)是G的一個子集，則Bi-Cayley圖是一個以G×{0，1}為點(diǎn)集，{{(g，0)，(gs，1)}，g∈G，s∈S}為邊集的二部圖。若圖X的每個最小邊割均

2、是某個點(diǎn)的關(guān)聯(lián)邊集，則稱圖X為超邊連通的。圖X的滿足去掉它后每個連通分支都至少有兩個點(diǎn)的邊割的最小基數(shù)稱為圖X的限制邊連通度。一個k-正則圖X被稱為最優(yōu)超邊連通的，若X是超邊連通的且X的限制邊連通度達(dá)到最大2k-2。在第二章中，我們證明了除偶圈外，所有連通Bi-Cayley圖都是最優(yōu)超邊連通的。第三章研究軌道數(shù)為2的k-正則連通圖的邊連通度，得到了如下結(jié)果：(1)確定了軌道數(shù)為2的3-正則和4-正則連通圖的邊連通度；(2)證明了對于給定

3、的正整數(shù)k和m，軌道數(shù)為2的k-正則m-邊連通圖的存在性；(3)在圍長大于等于5的前提下，軌道數(shù)為2的k-正則連通圖的邊連通度為正則度k。 第四章研究線圖和有向線圖的第二等周點(diǎn)連通度，得到了如下結(jié)果：(1)最小度大于等于2的強(qiáng)連通有向線圖的第二等周點(diǎn)連通度等于它的點(diǎn)連通度；(2)對于無向線圖，我們給出了第二等周點(diǎn)連通度存在的充要條件；(3)對于第二等周點(diǎn)連通度存在的無向線圖，它的第二等周點(diǎn)連通度或者等于限制點(diǎn)連通度或者等于最小度