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

图的点（边）连通分解及Kronecker乘积图的连通性问题

作　者: 王云
导　师: 宝音都仍
学　校: 新疆大学
专　业: 应用数学
关键词: 匹配 s-分解 Kronecker积 Cartesian积连通度
分类号: O157.5
类　型: 硕士论文
年　份: 2010年
下　载: 21次
引　用: 0次
阅　读: 论文下载

内容摘要

本文我们主要考虑一个连通图能否分解为一系列给定边(点)数的连通子图的问题.首先给出了在树T上能够3-边分解的充要条件C1(T-υ)≥C2(T-υ),这里的Gi(H)表示图H中连通分支满足顶点数模3等于i的连通分支的个数.然后又证明了每个连通图有{3,4}-边分解.设G为一个图.κ(G)表示G的连通度.用G×H表示图G和图H的Kronecker积.G×H的点集为集合V(G)×V(H),其中点(u，x)和(u，y)在G×H中相邻当且仅当uυ∈E(G)且xy∈E(H).Guji和、(?)umar (A note on the connectivity of Kronecker products of graphs,Appl.Math.Lett.22(2009)1360-1363.)猜测：对任意的非平凡图G,κ(G×Kn)=min{nκ(G),(n-1)δ(G)}其中n≥3.在这篇文章中我们将证明此猜想是正确的.本文共分为三章：第一章.介绍了s-分解及Kronecker积上连通性的背景知识.第二章.证明了一个连通图有{3,4}-边连通分解及树有3-边分解的充要条件.第三章.肯定了Kronecker乘积图中的猜想κ(G×Kn)=min{nκ(G),(n-1)δ(G)}其中n≥3.

全文目录

中文摘要  2-3
英文摘要  3-5
第一章序言  5-8
  §1.1 背景介绍  5-7
  §1.2 预备知识  7-8
第二章图的点(边)连通分解  8-15
  §2.1 引言  8-10
  §2.2 主要结果  10-15
第三章 Kronecker乘积图的连通性  15-20
  §3.1 引言  15-16
  §3.2 猜想的证明  16-20
参考文献  20-22
学术论文目录  22-23
致谢  23-24

图的点（边）连通分解及Kronecker乘积图的连通性问题

内容摘要

全文目录

相似论文