| 【中文题名】 | 图的某些连通性问题 |
| 【英文题名】 | Some Problems of the Connectivity of Graph |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2001-9-20 |
| 【中关键词】 | （k,g）-笼,不可分离圈,极小（k,l）边连通,等价类 |
| 【英关键词】 | （k,g）-cage, non-separating cycle, minimally （k,l）-edge-connected,,, equivalence class, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 |
（k;g）-笼是指具有围长g的k-正则图中那些顶点数最小的图。文[7]中给出了下面的猜
想：设G为一个（k;g）-笼，则它的每一个g-圈C是不可分离的（nonseparating）（也就是说，
对G中任意的g-圈C，G-C仍是连通的）。对于偶数g，文[7]已给出了此猜想的证明。本
文第二章将证明：对于奇数g，此猜想也是正确的。证明所使用的方法主要是反证法。
对于整数l≥2，图G的的l-边连通度定义为
其中ω(G-S)表示G_S的
连通分支数。特别地，如果l=2，则λ_2（G）=λ(G)。本文第三章将给出极小（k,k-1）-
边-连通图的一个充分必要条件并讨论此类图阶一定时边数的界。第三章的主要结果主要
有以下一些：
定理3.3 设G是连通图，|G|≥k-1，则G是极小（k,k-1）边连通的当且仅当下列都成立：
i）|B(G)|≤k-3；
ii）μ(G)≤k-|B(G)|-2；
iii）对(?)e∈E(G)-B(G)，有μ(G-e)≥k-|B(G)|-|[e]|... |
| 【论文题纲】 |
|
内容提要 |
3-5 |
|
英文摘要 |
5-8 |
|
第一章、 引言 |
8-10 |
|
1．1 符号说明 |
8-9 |
|
1．2 研究现状 |
9-10 |
|
第二章、 一个关于（k；g）-笼的猜想的证明 |
10-17 |
|
2．1 定以及引理 |
10-13 |
|
2．2 猜想的证明 |
13-17 |
|
第三章、 极小（k;k-1）-边连通图 |
17-32 |
|
3．1 定义及预备 |
17-19 |
|
3．2 充分必要条件及其推论 |
19-21 |
|
3．3 阶一定时边数的界 |
21-32 |
|
结束语 |
32-33 |
|
参考文献 |
33-35 |
|
致谢 |
35 |
|
| 【DOI】 | LunWen.ID:2.2008.11327 |
