On the Burkard-Hammer condition for hamiltonian split graphs

被引:6
作者
Tan, ND
Hung, LX
机构
[1] Inst Math, Hanoi 10307, Vietnam
[2] Prov Off Educ & Training, Tuyen Quang, Vietnam
关键词
split graph; Hamilton cycle; Burkard-Hammer condition;
D O I
10.1016/j.disc.2005.03.008
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A graph G = (V, E) is called a split graph if there exists a partition V = I boolean OR K such that the subgraphs of G induced by I and K are empty and complete graphs, respectively. In 1980, Burkard and Hammer gave a necessary but not sufficient condition for hamiltonian split graphs with vertical bar I vertical bar < vertical bar K vertical bar. In this paper, we show that the Burkard-Hammer condition is also sufficient for the existence of a Hamilton cycle in a split graph G such that 5 not equal vertical bar I vertical bar < vertical bar K vertical bar and the minimum degree delta(G) >= vertical bar I vertical bar - 3. For the case 5 = vertical bar I vertical bar < vertical bar K vertical bar, all split graphs satisfying the Burkard-Hammer condition but having no Hamilton cycles are also described. (c) 2005 Elsevier B.V. All rights reserved.
引用
收藏
页码:59 / 72
页数:14
相关论文
共 10 条
[1]  
Behzad M., 1971, INTRO THEORY GRAPHS
[2]   A NOTE ON HAMILTONIAN SPLIT GRAPHS [J].
BURKARD, RE ;
HAMMER, PL .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1980, 28 (02) :245-248
[3]  
Chvatal V., 1977, Ann. Discrete Math., V1, P145
[4]  
Foldes S., 1978, C MATH SOC J BOLYAI, V18, P331
[5]   Toughness, hamiltonicity and split graphs [J].
Kratsch, D ;
Lehel, J ;
Muller, H .
DISCRETE MATHEMATICS, 1996, 150 (1-3) :231-245
[6]  
Ngo Dac Tan, 2004, Discussiones Mathematicae Graph Theory, V24, P23, DOI 10.7151/dmgt.1210
[7]   NECESSARY CONDITIONS FOR HAMILTONIAN SPLIT GRAPHS [J].
PEEMOLLER, J .
DISCRETE MATHEMATICS, 1985, 54 (01) :39-47
[8]  
PELED UN, 1975, THESIS U WATERLOO, pCH6
[9]  
Stephane F., 1977, C NUMER, P311
[10]  
Tan ND, 2005, LECT NOTES COMPUT SC, V3330, P185