K-树图的可收缩边

发布时间：2019-07-11 20:43

【摘要】：图的连通性在图论的研究领域中是很重要的,它们对图论的发展有着重大的影响和推动作用.k-可收缩边是研究连通图的构造的强有力工具,在使用归纳证明连通图的性质也起着重要作用.k-树图是k连通图的一种,其有着诸多有趣的组合性质.很多NP-困难问题在有限的k-树图中都有多项式算法.本文以论文[2,7]为基础,定义了一个与k-树图G对应的新图T(G),单纯点集合S(G),RP-运算.研究了它们的性质、特征及与GC之间的关系,对k-树图的可收缩边导出子图的结构进行了研究,给出了k-树图可收缩边数目的下界,完全解决了k-树图可收缩边导出子图的连通度问题.主要结果有：1.k-树图可收缩边的计数.本文引入关于k-树的一个新的参数T(G),得到了k-树图G可收缩边数目更一般的下界与不可收缩边的数目的范围,并完全刻画了可收缩边数目恰为|G|+K-2的k-树图的结构特征.给出了T(G)中任意两点的距离与G中两点之间的距离关系式.2.k-树图收缩边导出子图的连通性.本文引入单纯点集合S(G)的概念,证明了κ(GC)=δ(Gc),当3≤δ(GC) k,Gc是超连通.3.k-树图导出图T(G)的结构特征.本文引入RP-运算,证明了Gc是k-正则当且仅当G是由两个特殊的k-树图通过RP-运算得到.
【学位授予单位】：广西师范学院
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5

【相似文献】

相关期刊论文 前10条

1 王金超;谷风;;图的邻接树图是哈密尔顿的[J];兰州交通大学学报;2007年03期

2 魏二玲;刘彦佩;;(邻接)树图的同构及平面性[J];数学进展;2009年02期

3 申石虎;;树图[J];东北重型机械学院学报;1980年01期

4 卜月华;;完全邻接树图的特征[J];浙江师范学院学报(自然科学版);1988年02期

5 黄容坤;;文图和树图在概率中的应用[J];河池师专学报(理科);1991年03期

6 刘儒英;关于不可约的T形树图[J];青海师专学报;1997年02期

7 杨春德;树图集散函数与中心的性质[J];重庆邮电学院学报;1998年03期

8 牛秋成;;利用树图法解排列题[J];数学学习与研究;2011年11期

9 张兰菊;邻接树图是哈密尔顿图猜想的一个等价命题(英文)[J];应用数学;2000年04期

10 李明哲;阶数最小的A(H)=4的非树图[J];哈尔滨师范大学自然科学学报;2003年05期

相关硕士学位论文 前10条

1 黄乐贤;K-树图的可收缩边[D];广西师范学院;2015年

2 刘秀国;伪树图的谱矩序列[D];湖北大学;2011年

3 杜建伟;1-树图的邻点可区别全染色[D];山西大学;2006年

4 高晶;树理论在分组测试中的应用[D];中国地质大学（北京）;2010年

5 李剑锋;可由其拉普拉斯谱确定的一些树图[D];湖南师范大学;2008年

6 白建甜;几类树图的能量及超能量图[D];广东工业大学;2008年

7 卞彩凤;准树图的最大广义Randi（？）指标[D];厦门大学;2009年

8 崔日升;广义Randi（？）指标在树图上的最大化问题[D];南开大学;2009年

9 刘鑫;有限树图上扩散算子的Borg-Levinson型定理[D];南京理工大学;2010年

10 谢笋;三角树图和K_4树图的Hosoya指标和Merrifield-Simmons指标研究[D];青海师范大学;2015年

，

本文编号：2513470