JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2015, Vol. 50 ›› Issue (10): 27-31.doi: 10.6040/j.issn.1671-9352.0.2015.072

Previous Articles     Next Articles

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

WANG Shan-shan, QI En-feng   

  1. 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

PDF (PC)

568

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

CLC Number: 

  • O157
[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.
[1] 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.
[2] YANG Zhao-xia . The contractible edges of the longest cycle in some 5-connected graphs [J]. J4, 2008, 43(6): 12-14 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd