【作者】 刘凤霞；

【导师】 孟吉翔；

【作者基本信息】 新疆大学 ， 应用数学， 2006， 硕士

【摘要】 连通度和边连通度是衡量网络可靠性的一个重要参数。作为经典连通度的推广，人们提出了条件(边)连通度。本文主要研究一些重要图类的条件(边)连通度。 第一章介绍了背景和一些基本概念。第二章主要研究Bi-Cayley图的超边连通性和最优超边连通性。设G是一个有限群，S(可以含有单位元)是G的一个子集，则Bi-cayley图是一个以G×{0，1)为点集，{{(g，0)，(gs，1)}，g∈G，s∈S}为边集的二部图。若图X的每个最小边割均是某个点的关联边集，则称图X为超边连通的。图X的满足去掉它后每个连通分支都至少有两个点的边割的最小基数称为图X的限制边连通度。一个k-正则图X被称为最优超边连通的，若X是超边连通的且X的限制边连通度达到最大2k-2。在第二章中，我们证明了除偶圈外，所有连通Bi-Cayley图都是最优超边连通的。 第三章研究轨道数为2的k-正则连通图的边连通度，得到了如下结果：(1)确定了轨道数为2的3-正则和4-正则连通图的边连通度；(2)证明了对于给定的正整数k和m，轨道数为2的k-正则m-边连通图的存在性；(3)在围长大于等于5的前提下，轨道数为2的k-正则连通图的边连通度为正则度k。 第四章研究线图和有向线图的第二等周点连通度，得到了如下结果：(1)最小度大于等于2的强连通有向线图的第二等周点连通度等于它的点连通度；(2)对于无向线图，我们给出了第二等周点连通度存在的充要条件；(3)对于第二等周点连通度存在的无向线图，它的第二等周点连通度或者等于限制点连通度或者等于最小度和次最小度的和。更多还原

【Abstract】 The connectivity and edge connectivity axe important measure of the network’s reliability. As a generalization of classical (edge) connectivity, the concept of conditional (edge) connectivity has been proposed. In this thesis, we study the conditional (edge) connectivity for some important classes of graphs.In chapter one, we introduce the background and terminology. Chapter two is devoted to studying super-edge-connected and optimally super-edge-connected Bi-Cayley graphs. Let G be a finite group, 5(possibly, contains the identity element) be a subset of G. The Bi-Cayley graph BC(G, S) is a bipartite graph with vertex set G × {0,1} and edge set {{(g, 0), (gs, 1)}, g ∈ G, s ∈ S}. A graph X is said to be super-edge-connected if every minimum edge cut of X is a set of edges incident with some vertex. The restricted edge connectivity λ’(X) of X is the minimum number of edges whose removal disconnects X into nontrivial components. A k-regular graph X is said to be optimally super-edge-connected if X is super-edge-connected and its restricted edge connectivity attains the maximum 2k — 2. In chapter two, we show that all connected Bi-Cayley graphs, except even cycles, are optimally super-edge-connected.In chapter three, we study the edge connectivity of k-regular connected graph with two orbits. The following results are obtained: (a) The edge connectivity of 3-regular and 4-regular connected graphs with two orbits is determined; (b) we prove the existence of k-regular m-edge-connected graphs with two orbits for some given positive integers k and m; (c) The edge connectivity of a k-regular connected graph with two orbits and girth ≥ 5 attains its regular degree k.In chapter four, we study the second isoperimetric connectivity of line graphs and line digraphs. For line digraphs, we show that the second isoperimetric connectivity of strongly connected line digraphs with δ ≥ 2 equals its connectivity. For line graphs, we give a sufficient and necessary condition for the existence of the second isoperimetric connectivity, and we show that under the condition that the second isoperimetric connectivity exists, the second isoperimetric con-更多还原