k-连通图中最长圈上可收缩边的数目

doi:10.6040/j.issn.1671-9352.0.2015.072

山东大学学报（理学版） ›› 2015, Vol. 50 ›› Issue (10): 27-31.doi: 10.6040/j.issn.1671-9352.0.2015.072

k-连通图中最长圈上可收缩边的数目

王珊珊, 齐恩凤

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

收稿日期:2015-02-27 修回日期:2015-09-08 出版日期:2015-10-20 发布日期:2015-10-21
作者简介:王珊珊(1991-),女,硕士研究生,研究方向为图论.E-mail:shanshan11299@163.com
基金资助:
国家自然科学基金资助项目(11471193)

On the number of contractible edges of longest cycles in k-connected graphs

WANG Shan-shan, QI En-feng

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

Received:2015-02-27 Revised:2015-09-08 Online:2015-10-20 Published:2015-10-21

摘要/Abstract

摘要： 给出了k-连通图中最长圈上的可收缩边的数目,得到如下结果:任意断片的阶至少为「k/2+1 的k-连通图中最长圈上至少有3 条可收缩边;更进一步,若该k-连通图中存在哈密顿圈,则哈密顿圈上至少有6 条可收缩边。

关键词: 最长圈, 可收缩边, k-连通图, 哈密顿圈

Abstract: The number of contractible edges of longest cycles in k-connected graphs is given. The conclusions are that if every fragment of a k-connected graph has an order at least 「k/2+1,then there exist at least three contractible edges on the longest cycle of this graph. Furthermore, if this graph has a hamiltonian cycle, then there exist at least six contractible edges on the hamiltonian cycle.

Key words: contractible edge, hamiltonian cycle, k-connected graph, longest cycle

中图分类号:

O157

王珊珊, 齐恩凤. k-连通图中最长圈上可收缩边的数目[J]. 山东大学学报（理学版）, 2015, 50(10): 27-31.

WANG Shan-shan, QI En-feng. 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.

参考文献

[1] BONDY J A, MURTY U S R. Graph theory with applications[M]. London: The Macmillan Press Ltd, 1976.
[2] TUTTE W T. A theory of 3-connected graphs[J]. Indag Math, 1961, 23:441-455.
[3] THOMASSEN C. Non-separating cycles in k-connected graphs[J]. Graph Theory, 1981, 5:351-354.
[4] EGAWA Y. Contractible edges in n-connected graphs with minimum degree greater than or equal to[5n/4][J]. Graphs and Combinatorics, 1990, 7:15-21.
[5] 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.
[6] KRISELL M. A survey on contractible edges in graph of a prescribed vertex connectivity[J]. Graphs and Combinatorics, 2002, 18(1):1-30.
[7] 杨朝霞. 某些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: Naturnal Science, 2008, 43(6):12-14.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

k-连通图中最长圈上可收缩边的数目

On the number of contractible edges of longest cycles in k-connected graphs

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

多维度评价

本文评价

推荐阅读 0

[1]	王倩. k-连通图中生成树和完美匹配上的可收缩边[J]. 山东大学学报（理学版）, 2016, 51(8): 29-34.
[2]	杨朝霞 . 某些5-连通图中最长圈上的可收缩边[J]. J4, 2008, 43(6): 12-14 .