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

doi:10.6040/j.issn.1671-9352.0.2016.148

山东大学学报（理学版） ›› 2016, Vol. 51 ›› Issue (8): 29-34.doi: 10.6040/j.issn.1671-9352.0.2016.148

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

王倩

山东大学数学学院, 山东济南 250100

收稿日期:2016-04-06 出版日期:2016-08-20 发布日期:2016-08-08
作者简介:王倩(1992— ),女,硕士研究生,主要研究方向为图论. E-mail:wangqian_sdu@163.com
基金资助:
国家自然科学基金资助项目(61432010)

The contractible edges of a spanning tree and a perfect matching in k-connected graphs

WANG Qian

School of Mathematics, Shandong University, Jinan 250100, Shandong, China

Received:2016-04-06 Online:2016-08-20 Published:2016-08-08

摘要/Abstract

摘要： 给出了k-连通图生成树和完美匹配上的可收缩边数目,得到如下结果:任意断片的阶都大于「k/2的k-连通图中生成树上至少有4条可收缩边;若该k-连通图中存在完美匹配,则完美匹配上至少有「k/2+1条可收缩边。

关键词: k-连通图, 可收缩边, 生成树, 完美匹配

Abstract: The numbers of contractible edges of a spanning tree and a perfect matching in k-connected graphs are given. The conclusions are that if every fragment of a k-connected graph has an order more than 「k/2, then there exist at least four contractible edges on the spanning tree of this graph. Furthermore, if this graph has a perfect matching, then there exist at least 「k/2+1 contractible edges on the perfect matching.

Key words: contractible edge, perfect matching, k-connect graph, spanning tree

中图分类号:

O157

王倩. k-连通图中生成树和完美匹配上的可收缩边[J]. 山东大学学报（理学版）, 2016, 51(8): 29-34.

WANG Qian. The contractible edges of a spanning tree and a perfect matching in k-connected graphs[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(8): 29-34.

参考文献

[1] BONDY J A, MURTY U S R. Graph theory with applications [M]. London: The Macmillan Press Ltd, 1976.
[2] MARTIONV N. Uncontractible 4-connected graphs[J]. Graph Theory, 1982, 6(3):343-344.
[3] KRIESELL M. A degree sum condition for the existence of a contractible edge in a k-connected graph[J]. Comb Theory Ser, 2001, B82:81-101.
[4] 王珊珊.k-连通图中最长圈上可收缩边的数目[J].山东大学学报(理学版),2015,50(10):27-31. WANG Shanshan. On the number of contractible edges of longest cycles in k-connected graphs[J]. Journal of Shandong University(Natural Science), 2015, 50(10):27-31.
[5] KRIESELL M. A survey on contractible edges in graph of a prescribed vertex connectivity[J]. Graphs and Combinatorics, 2002, 18(1):1-30.
[6] TUTTE W T.A theory of 3-connected graphs[J]. Indag Math, 1961, 23:441-455.
[7] DEAN N. Distribution of contractible edges in k-connected graphs[J]. Comb. Theory, Ser.B, 1990, 48:1-5.
[8] EGAWA Y. Contractible edges in n-connected graphs with minimum degree greater than or equal to[5n/4] [J]. Graphs Comb, 1990, 7:15-21.
[9] 杨朝霞.某些5-连通图中最长圈上的可收缩边[J].山东大学学报(理学版),2008,43(6):12-14. YANG Zhaoxia. The contractible edges of the longest cycle in some 5-connected graphs[J]. Journal of Shandong University(Natural Science), 2008, 43(6):12-14.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

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

The contractible edges of a spanning tree and a perfect matching in k-connected graphs

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

多维度评价

本文评价

推荐阅读 0

[1]	王珊珊, 齐恩凤. k-连通图中最长圈上可收缩边的数目[J]. 山东大学学报（理学版）, 2015, 50(10): 27-31.
[2]	姚明1,姚兵2*,陈祥恩2. 立方Halin图的完备色数[J]. J4, 2012, 47(2): 65-70.
[3]	肖海强1,2，张昭1*. λ_3,q-连通图的刻画[J]. J4, 2010, 45(6): 27-30.
[4]	王洪伟. 二部图匹配强迫数的谱[J]. J4, 2009, 44(12): 30-35.
[5]	杨朝霞 . 某些5-连通图中最长圈上的可收缩边[J]. J4, 2008, 43(6): 12-14 .