学位论文 > 优秀研究生学位论文题录展示

一些重要图类的条件连通度

作　者: 刘凤霞
导　师: 孟吉翔
学　校: 新疆大学
专　业: 应用数学
关键词: 超边连通性最优超边连通性 Bi-Cayley图轨道第二等周点连通度
分类号: O157.5
类　型: 硕士论文
年　份: 2006年
下　载: 53次
引　用: 0次
阅　读: 论文下载

内容摘要

连通度和边连通度是衡量网络可靠性的一个重要参数。作为经典连通度的推广，人们提出了条件(边)连通度。本文主要研究一些重要图类的条件(边)连通度。第一章介绍了背景和一些基本概念。第二章主要研究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)对于第二等周点连通度存在的无向线图，它的第二等周点连通度或者等于限制点连通度或者等于最小度和次最小度的和。

全文目录

Chinese abstract  3-4
English abstract  4-6
1. Introduction  6-10
2. Super-edge-connected and optimally super-edge-connected Bi-Cayley graphs  10-20
  2.1 Super-edge-connected Bi-Cayley graphs  10-15
  2.2 Optimally super-edge-connected Bi-Cayley graphs  15-20
3. Edge-connectivity of k-regular connected graphs with two orbits  20-30
  3.1 Some preliminaries  20-25
  3.2 The main results  25-30
4. The second isoperimetric connectivity of line graphs and line digraphs  30-34
  4.1 The second isoperimetric connectivity of line digraphs  30-32
  4.2 The second isoperimetric connectivity of line graphs  32-34
5. References  34-37
6. Contents of finished papers  37-38
7. Acknowledgement  38-39
学位论文独创性声明  39
学位论文知识产权权属声明  39

一些重要图类的条件连通度

内容摘要

全文目录

相似论文