Long cycles in 4-connected planar graphs

被引：8

作者：

Cui, Qing ^{[1
]}

Hu, Yumei ^{[1
,2
]}

Wang, Jian ^{[1
]}

机构：

[1] Nankai Univ, Ctr Combinator, LPMC TJKLC, Tianjin 300071, Peoples R China

[2] Tianjin Univ, Dept Math, Tianjin 300072, Peoples R China

来源：

DISCRETE MATHEMATICS | 2009年 / 309卷 / 05期

基金：

美国国家科学基金会;

关键词：

Hamilton cycle; Tutte path; Contractible subgraph; PATHS;

D O I：

10.1016/j.disc.2007.11.059

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G be a 4-connected planar graph on n vertices. Malkevitch conjectured that if G contains a cycle of length 4, then G contains a cycle of length k for every k is an element of {n, n - 1, ... , 3}. This conjecture is true for every k is an element of {n, n - 1, ... , n - 6} with k >= 3. In this paper, we prove that G also has a cycle of length it - 7 provided n >= 10. (C) 2007 Elsevier B.V. All rights reserved.

引用

页码：1051 / 1059

页数：9

共 12 条

[1]

[Anonymous], 1963, Proceedings of the London Mathematical Society

[2]

[Anonymous], 1931, Ann. Math., DOI DOI 10.2307/1968197

[3] Cycles in 4-connected planar graphs [J].

Chen, GT ;

Fan, GH ;

Yu, XX .

EUROPEAN JOURNAL OF COMBINATORICS, 2004, 25 (06) :763-780

[4]

Malkevitch Joseph., 1988, Selected topics in graph theory 3, P169

[5] UNCONTRACTABLE 4-CONNECTED GRAPHS [J].

MARTINOV, N .

JOURNAL OF GRAPH THEORY, 1982, 6 (03) :343-344

[6]

Sanders DP, 1996, J GRAPH THEOR, V21, P43, DOI 10.1002/(SICI)1097-0118(199601)21:1<43::AID-JGT6>3.0.CO

[7]

2-M

[8]

Sanders DP, 1997, J GRAPH THEOR, V24, P341, DOI 10.1002/(SICI)1097-0118(199704)24:4<341::AID-JGT6>3.0.CO

[9]

2-O

[10] 4-CONNECTED PROJECTIVE-PLANAR GRAPHS ARE HAMILTONIAN [J].

THOMAS, R ;

YU, XX .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1994, 62 (01) :114-132

← 1 2 →