Independent dominating sets and a second Hamiltonian cycle in regular graphs

被引：25

作者：

Thomassen, C ^{[1
]}

机构：

[1] Tech Univ Denmark, Dept Math, DK-2800 Lyngby, Denmark

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 1998年 / 72卷 / 01期

关键词：

D O I：

10.1006/jctb.1997.1794

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In 1975, John Sheehan conjectured that every Hamiltonian 4-regular graph has a second Hamiltonian cycle. Combined with earlier results this would imply that every Hamiltonian r-regular graph (r greater than or equal to 3) has a second Hamiltonian cycle, We shall verify this for r greater than or equal to 300. (C) 1998 Academic Press.

引用

页码：104 / 109

页数：6

共 12 条

[1]

BONDY J. A, 1995, HDB COMBINATORICS, P3

[2] ON EDGE-HAMILTONIAN PROPERTY OF CAYLEY-GRAPHS [J].

CHEN, CC .

DISCRETE MATHEMATICS, 1988, 72 (1-3) :29-33

[3] SPANNING CYCLES OF NEARLY CUBIC GRAPHS [J].

ENTRINGER, RC ;

SWART, H .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1980, 29 (03) :303-309

[4]

Erdos P., 1975, INFINITE FINITE SETS, V10, P609

[5] A SOLUTION TO A COLORING PROBLEM OF ERDOS,P. [J].

FLEISCHNER, H ;

STIEBITZ, M .

DISCRETE MATHEMATICS, 1992, 101 (1-3) :39-48

[6] UNIQUENESS OF MAXIMAL DOMINATING CYCLES IN 3-REGULAR GRAPHS AND OF HAMILTONIAN CYCLES IN 4-REGULAR GRAPHS [J].

FLEISCHNER, H .

JOURNAL OF GRAPH THEORY, 1994, 18 (05) :449-459

[7]

Graham R.L., 1980, Ramsey Theory, V2nd

[8]

Sheehan J., 1975, RECENT ADV GRAPH THE, P447

[9]

THOMASON AG, 1978, ANN DISCRETE MATH, V3, P259

[10] Chords of longest cycles in cubic graphs [J].

Thomassen, C .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1997, 71 (02) :211-214

← 1 2 →