| 【中文题名】 | 跳图的完美匹配和1-坚韧度 |
| 【英文题名】 | On Perfect Matchings and 1-toughness of Jump Graphs |
| 【学科专业】 | 基础数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2006-11-8 |
| 【中关键词】 | 跳图,完美匹配,坚韧度,,, |
| 【英关键词】 | Jump graph,Perfect matching,Toughness, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 | 线图是一类重要的变换图，已被广泛研究。我们称线图的补图为跳图。与丰富的线图理论相比较，跳图的已知结果较少。对于一个简单图G，吴和王(Graph Theory Notes of New York 39(2000)23-25)给出了G的跳图有完美匹配的充分必要条件。在这篇论文中，我们利用Tutte定理(一个图有完美匹配的充分必要条件)把这个结果加以推广，给出了可以有重边的无环图G的跳图有完美匹配的充分必要条件。该结果的证明基于跳图J(G)不连通时，G的底图(?)的结构的详细刻画。
一个图G称作1-tough，如果对于顶点集V(G)的每一个非空真子集S，都有ω(G—S)≤|S|，这里ω(G—S)表示G—S的连通分支数。在这篇论文中，我们也给出了可以有重边的无环图G的跳图是1-tough的充分必要条件。
在给出主要结果之前，我们需要一些记号。设G是一个无环图，我们用ε(G)表示G的边数，△(G)表示G的最大度，H(?)G表示H是G的一个子图。▽(G)表示G中底图与K_3同构的子图的最大边数，若这样的子图不存在，则▽(G)=0。G中的一条边e称为控制边，如果它与G中其它的边都相邻。D(G... |
| 【论文题纲】 |
|
摘要 |
2-3 |
|
Abstract |
3-6 |
|
1. Introduction |
6-9 |
|
2. Connectedness of jump graphs |
9-13 |
|
3. Proof of Theorem 1.2 |
13-18 |
|
4. 1-toughness |
18-23 |
|
5. Concluding remarks |
23-24 |
|
6. References |
24-25 |
|
7. Contents of finished papers |
25-26 |
|
8. Acknowledgement |
26-27 |
|
学位论文独创性声明 |
27 |
|
学位论文知识产权权属声明 |
27 |
|
| 【DOI】 | LunWen.ID:2.2008.11727 |
