Hamilton cycles in split graphs with large minimum degree

Ngo Dac Tan; Le Xuan Hung

Discussiones Mathematicae Graph Theory (2004)

  • Volume: 24, Issue: 1, page 23-40
  • ISSN: 2083-5892

Abstract

top
A graph G is called a split graph if the vertex-set V of G can be partitioned into two subsets V₁ and V₂ such that the subgraphs of G induced by V₁ and V₂ are empty and complete, respectively. In this paper, we characterize hamiltonian graphs in the class of split graphs with minimum degree δ at least |V₁| - 2.

How to cite

top

Ngo Dac Tan, and Le Xuan Hung. "Hamilton cycles in split graphs with large minimum degree." Discussiones Mathematicae Graph Theory 24.1 (2004): 23-40. <http://eudml.org/doc/270580>.

@article{NgoDacTan2004,
abstract = {A graph G is called a split graph if the vertex-set V of G can be partitioned into two subsets V₁ and V₂ such that the subgraphs of G induced by V₁ and V₂ are empty and complete, respectively. In this paper, we characterize hamiltonian graphs in the class of split graphs with minimum degree δ at least |V₁| - 2.},
author = {Ngo Dac Tan, Le Xuan Hung},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Hamilton cycle; split graph; bipartite graph; Hamiltonian graphs},
language = {eng},
number = {1},
pages = {23-40},
title = {Hamilton cycles in split graphs with large minimum degree},
url = {http://eudml.org/doc/270580},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Ngo Dac Tan
AU - Le Xuan Hung
TI - Hamilton cycles in split graphs with large minimum degree
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 1
SP - 23
EP - 40
AB - A graph G is called a split graph if the vertex-set V of G can be partitioned into two subsets V₁ and V₂ such that the subgraphs of G induced by V₁ and V₂ are empty and complete, respectively. In this paper, we characterize hamiltonian graphs in the class of split graphs with minimum degree δ at least |V₁| - 2.
LA - eng
KW - Hamilton cycle; split graph; bipartite graph; Hamiltonian graphs
UR - http://eudml.org/doc/270580
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 28 (1980) 245-248, doi: 10.1016/0095-8956(80)90069-6. Zbl0403.05058
  3. [3] V. Chvatal, New directions in hamiltonian graph theory, in: New directions in the theory of graphs (Proc. Third Ann Arbor Conf. Graph Theory, Univ. Michigan, Ann Arbor, Mich., 1971), pp. 65-95, Acad. Press, NY 1973. 
  4. [4] V. Chvatal and P. Erdős, A note on hamiltonian circiuts, Discrete Math. 2 (1972) 111-113, doi: 10.1016/0012-365X(72)90079-9. Zbl0233.05123
  5. [5] V. Chvatal 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
  6. [6] S. Foldes, 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), 311-315. Congressus Numerantium, No XIX, Utilitas Math., Winnipeg, Man., 1977. Zbl0407.05071
  7. [7] S. Foldes 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). 
  8. [8] R.J. Gould, Updating the hamiltonian problem, a survey, J. Graph Theory 15 (1991) 121-157, doi: 10.1002/jgt.3190150204. Zbl0746.05039
  9. [9] P. Hall, On representatives of subsets, J. London Math. Soc. 10 (1935) 26-30, doi: 10.1112/jlms/s1-10.37.26. Zbl0010.34503
  10. [10] F. Harary and U. Peled, Hamiltonian threshold graphs, Discrete Appl. Math. 16 (1987) 11-15, doi: 10.1016/0166-218X(87)90050-3. Zbl0601.05033
  11. [11] B. Jackson and O. Ordaz, Chvatal-Erdős conditions for paths and cycles in graphs and digraphs, a survey, Discrete Math. 84 (1990) 241-254, doi: 10.1016/0012-365X(90)90130-A. Zbl0726.05043
  12. [12] J. Peemöller, Necessary conditions for hamiltonian split graphs, Discrete Math. 54 (1985) 39-47. Zbl0563.05041
  13. [13] U.N. Peled, Regular Boolean functions and their polytope, Chapter VI (Ph. D. Thesis, Univ. of Waterloo, Dep. Combin. and Optimization, 1975). 
  14. [14] S.B. Rao, Solution of the hamiltonian problem for self-complementary graphs, J. Combin. Theory (B) 27 (1979) 13-41, doi: 10.1016/0095-8956(79)90065-0. Zbl0406.05047

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.