Square Hamiltonian cycles in graphs with maximal 4-cliques

被引：2

作者：

Kierstead, HA ^{[1
]}

Quintana, J ^{[1
]}

机构：

[1] ARIZONA STATE UNIV,DEPT MATH,TEMPE,AZ 85287

来源：

DISCRETE MATHEMATICS | 1998年 / 178卷 / 1-3期

关键词：

D O I：

10.1016/S0012-365X(97)81819-5

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The square of a graph is obtained by adding additional edges joining all pairs of vertices with distance two in the original graph. Posa conjectured that if G is a simple graph on n vertices with minimum degree 2n/3, then G contains the square of a hamiltonian cycle. We show that Posa's conjecture holds for graphs that in addition contain a maximal 4-clique.

引用

页码：81 / 92

页数：12

共 9 条

[1] [Anonymous], 1952, P LOND MATH SOC
[2] Erdos P., 1964, Problem 9, Theory of Graphs and its Applications, P159
[3] FAN G, 1994, SIAM J DISCRETE MATH, P203
[4] Hamiltonian square-paths
Fan, GH
Kierstead, HA
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1996, 67 (02) : 167 - 182
[5] Fan GH, 1996, J GRAPH THEOR, V23, P241, DOI 10.1002/(SICI)1097-0118(199611)23:3<241::AID-JGT4>3.3.CO
[6] 2-K
[7] THE SQUARE OF PATHS AND CYCLES
FAN, GH
KIERSTEAD, HA
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1995, 63 (01) : 55 - 64
[8] KOMLOS J, SQUARE HAMILTONIAN C
[9] Seymour P., 1974, Combinatorics, P201

← 1 →