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

Abstract

top
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.

How to cite

top

Ngo 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. [1] M. Behzad and G. Chartrand, Introduction to the theory of graphs (Allyn and Bacon, Boston, 1971). Zbl0238.05101
  2. [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. [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. [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. [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. [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. [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. [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. [9] J. Peemöller, Necessary conditions for hamiltonian split graphs, Discrete Math. 54 (1985) 39-47. Zbl0563.05041
  10. [10] U.N. Peled, Regular Boolean functions and their polytope, Chap VI, Ph. D. Thesis (Univ. of Waterloo, Dept. Combin. and Optimization, 1975). 
  11. [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. [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. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.