k-连通图中生成树和完美匹配上的可收缩边

发布时间：2018-03-25 00:17

  本文选题：k-连通图　切入点：可收缩边　出处：《山东大学学报(理学版)》2016年08期

【摘要】：给出了k-连通图生成树和完美匹配上的可收缩边数目,得到如下结果:任意断片的阶都大于「k/2■的k-连通图中生成树上至少有4条可收缩边;若该k-连通图中存在完美匹配,则完美匹配上至少有「k/2■+1条可收缩边。
[Abstract]:In this paper, the number of contractible edges on the spanning tree and perfect matching of k-connected graphs is given. The following results are obtained: there are at least four contractible edges on the spanning tree of a kconnected graph whose order of any fragment is greater than "k / 2", if there is a perfect match in the k-connected graph, The perfect match has at least "k / 21 retractable edges".
【作者单位】： 山东大学数学学院;
【基金】：国家自然科学基金资助项目(61432010)
【分类号】：O157.5

【相似文献】

相关期刊论文 前10条

1 谢果;判定k-点连通图与k-边连通图极小性的定理[J];四川师范大学学报(自然科学版);2000年05期

2 余世群;一类极大临界h连通图的性质[J];湖北民族学院学报(自然科学版);2002年04期

3 齐登记,余世群;收缩临界6-连通图中的6度点[J];湖北民族学院学报(自然科学版);2002年04期

4 赵克文,曾克扬;哈密尔顿连通图的一点注记[J];工程数学学报;2003年02期

5 赵克文;哈密尔顿连通图与邻域并条件[J];信息工程大学学报;2003年02期

6 余世群;一类极大临界2连通图的结构[J];湖北民族学院学报(自然科学版);2004年04期

7 陈仪朝,苏健基;恰含5条非基本边的极小3连通图[J];广西师范大学学报(自然科学版);2004年03期

8 林福财;关于4连通图的容错直径和宽直径[J];漳州师范学院学报(自然科学版);2005年01期

9 余世群;;一类极大临界4连通图的结构[J];湖北民族学院学报(自然科学版);2006年02期

10 刘育兴;苏健基;;恰有k条非基本边的极小3连通图[J];数学研究与评论;2006年04期

相关会议论文 前1条

1 张薇;张立辉;乞建勋;李星梅;苏志雄;;带正权的无向连通图中最短路问题研究[A];中国运筹学会第九届学术交流会论文集[C];2008年

相关博士学位论文 前10条

1 罗朝阳;图的点度与距离型拓扑指标参数及其应用[D];山东大学;2015年

2 吴亚平;k-连通图中最长圈及余直径研究[D];华中师范大学;2011年

3 康海燕;连通图中可去边和圈的研究[D];山东大学;2010年

4 刘素娟;2-（边-）连通图的彩虹连通数[D];南开大学;2013年

5 陈晓东;无爪图及其扩展图的Hamilton性[D];大连理工大学;2012年

6 侯新民;网络（图）广义直径的研究[D];大连理工大学;2002年

7 蔡建生;图的因子和分数因子[D];山东大学;2007年

8 梁浩;图的拉普拉斯矩阵和临界群[D];中国科学技术大学;2009年

9 洪振木;某些网络可靠性和有效性研究[D];中国科学技术大学;2014年

10 Alaa Amer Najim;关于图的边添加和边减少问题研究[D];中国科学技术大学;2006年

相关硕士学位论文 前10条

1 齐恩凤;k-连通图的可收缩边和可收缩圈[D];广西师范大学;2006年

2 余世群;一类极大临界h连通图的结构[D];广西师范大学;2003年

3 覃城阜;收缩临界5-连通图的性质[D];广西师范大学;2004年

4 杨迎球;k连通图中的k可收缩边[D];广西师范大学;2007年

5 张志芳;6连通图中的可收缩边[D];河南师范大学;2011年

6 毕振明;恰含6条非基本边的极小3连通图[D];山东大学;2012年

7 王雪;7-连通图最长圈上的可收缩边及3-连通图可收缩非边的分布[D];山东大学;2013年

8 崔燕飞;连通图中可收缩边的分布[D];山西大学;2014年

9 洪艳梅;极小限制性边连通图的最优性和超边连通图的容错性[D];新疆大学;2009年

10 陈新卫;收缩临界k连通图中的原子及阶较小的端片[D];广西师范大学;2007年

，

本文编号：1660698