# A classification for maximal nonhamiltonian Burkard-Hammer graphs

Ngo Dac Tan; Chawalit Iamjaroen

Discussiones Mathematicae Graph Theory (2008)

- Volume: 28, Issue: 1, page 67-89
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topNgo Dac Tan, and Chawalit Iamjaroen. "A classification for maximal nonhamiltonian Burkard-Hammer graphs." Discussiones Mathematicae Graph Theory 28.1 (2008): 67-89. <http://eudml.org/doc/270255>.

@article{NgoDacTan2008,

abstract = {A graph G = (V,E) is called a split graph if there exists a partition V = I∪K such that the subgraphs G[I] and G[K] of G induced by I and K are empty and complete graphs, respectively. In 1980, Burkard and Hammer gave a necessary condition for a split graph G with |I| < |K| to be hamiltonian. We will call a split graph G with |I| < |K| satisfying this condition a Burkard-Hammer graph. Further, a split graph G is called a maximal nonhamiltonian split graph if G is nonhamiltonian but G+uv is hamiltonian for every uv ∉ E where u ∈ I and v ∈ K. Recently, Ngo Dac Tan and Le Xuan Hung have classified maximal nonhamiltonian Burkard-Hammer graphs G with minimum degree δ(G) ≥ |I|- 3. In this paper, we classify maximal nonhamiltonian Burkard-Hammer graphs G with |I| ≠ 6,7 and δ(G) = |I| - 4.},

author = {Ngo Dac Tan, Chawalit Iamjaroen},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {split graph; Burkard-Hammer condition; Burkard-Hammer graph; hamiltonian graph; maximal nonhamiltonian split graph; Hamiltonian graph; maximal non-Hamiltonian split graph},

language = {eng},

number = {1},

pages = {67-89},

title = {A classification for maximal nonhamiltonian Burkard-Hammer graphs},

url = {http://eudml.org/doc/270255},

volume = {28},

year = {2008},

}

TY - JOUR

AU - Ngo Dac Tan

AU - Chawalit Iamjaroen

TI - A classification for maximal nonhamiltonian Burkard-Hammer graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2008

VL - 28

IS - 1

SP - 67

EP - 89

AB - A graph G = (V,E) is called a split graph if there exists a partition V = I∪K such that the subgraphs G[I] and G[K] of G induced by I and K are empty and complete graphs, respectively. In 1980, Burkard and Hammer gave a necessary condition for a split graph G with |I| < |K| to be hamiltonian. We will call a split graph G with |I| < |K| satisfying this condition a Burkard-Hammer graph. Further, a split graph G is called a maximal nonhamiltonian split graph if G is nonhamiltonian but G+uv is hamiltonian for every uv ∉ E where u ∈ I and v ∈ K. Recently, Ngo Dac Tan and Le Xuan Hung have classified maximal nonhamiltonian Burkard-Hammer graphs G with minimum degree δ(G) ≥ |I|- 3. In this paper, we classify maximal nonhamiltonian Burkard-Hammer graphs G with |I| ≠ 6,7 and δ(G) = |I| - 4.

LA - eng

KW - split graph; Burkard-Hammer condition; Burkard-Hammer graph; hamiltonian graph; maximal nonhamiltonian split graph; Hamiltonian graph; maximal non-Hamiltonian split graph

UR - http://eudml.org/doc/270255

ER -

## References

top- [1] M. Behzad and G. Chartrand, Introduction to the theory of graphs (Allyn and Bacon, Boston, 1971). Zbl0238.05101
- [2] R.E. Burkard and P.L. Hammer, A note on hamiltonian split graphs, J. Combin. Theory (B) 28 (1980) 245-248, doi: 10.1016/0095-8956(80)90069-6. Zbl0403.05058
- [3] V. Chvátal and P.L. Hammer, Aggregation of inequalities in integer programming, Ann. Discrete Math. 1 (1977) 145-162, doi: 10.1016/S0167-5060(08)70731-3. Zbl0384.90091
- [4] S. Földes and P.L. Hammer, Split graphs, in: Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La, 1977) pp. 311-315. Congr. Numer., No. XIX, Utilitas Math., Winnipeg, Man. 1977. Zbl0407.05071
- [5] S. Földes and P.L. Hammer, On a class of matroid-producing graphs, in: Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely 1976) Vol. 1, 331-352, Colloq. Math. Soc. Janós Bolyai 18 (North-Holland, Amsterdam-New York, 1978). Zbl0395.05021
- [6] P.B. Henderson and Y. Zalcstein, A graph-theoretic characterization of the PV_{chunk} class of synchronizing primitive, SIAM J. Computing 6 (1977) 88-108, doi: 10.1137/0206008. Zbl0349.68022
- [7] A.H. Hesham and El.R. Hesham, Task allocation in distributed systems: a split graph model, J. Combin. Math. Combin. Comput. 14 (1993) 15-32.
- [8] D. Kratsch, J. Lehel and H. Müller, Toughness, hamiltonicity and split graphs, Discrete Math. 150 (1996) 231-245, doi: 10.1016/0012-365X(95)00190-8. Zbl0855.05079
- [9] J. Peemöller, Necessary conditions for hamiltonian split graphs, Discrete Math. 54 (1985) 39-47. Zbl0563.05041
- [10] U.N. Peled, Regular Boolean functions and their polytope, Chap VI, Ph. D. Thesis (Univ. of Waterloo, Dept. Combin. and Optimization, 1975).
- [11] Ngo Dac Tan and Le Xuan Hung, Hamilton cycles in split graphs with large minimum degree, Discuss. Math. Graph Theory 24 (2004) 23-40, doi: 10.7151/dmgt.1210. Zbl1054.05064
- [12] Ngo Dac Tan and Le Xuan Hung, On the Burkard-Hammer condition for hamiltonian split graphs, Discrete Math. 296 (2005) 59-72, doi: 10.1016/j.disc.2005.03.008. Zbl1075.05051
- [13] Ngo Dac Tan and C. Iamjaroen, Constructions for nonhamiltonian Burkard-Hammer graphs, in: Combinatorial Geometry and Graph Theory (Proc. of Indonesia-Japan Joint Conf., September 13-16, 2003, Bandung, Indonesia) 185-199, Lecture Notes in Computer Science 3330 (Springer, Berlin Heidelberg, 2005). Zbl1117.05073
- [14] Ngo Dac Tan and C. Iamjaroen, A necessary condition for maximal nonhamiltonian Burkard-Hammer graphs, J. Discrete Math. Sciences & Cryptography 9 (2006) 235-252. Zbl1103.05046

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.