Abstract
One of the earliest results about hamiltonian graphs was given by Dirac. He showed that if a graphG has orderp and minimum degree at least\(\frac{p}{2}\) thenG is hamiltonian. Moon and Moser showed that a balanced bipartite graph (the two partite sets have the same order)G has orderp and minimum degree more than\(\frac{p}{4}\) thenG is hamiltonian. In this paper, their idea is generalized tok-partite graphs and the following result is obtained: LetG be a balancedk-partite graph with orderp = kn. If the minimum degree
thenG is hamiltonian. The result is best possible.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Dirac, G.: Some theorems on abstract graphs. Proc. London Math Soc.2, 69–81 (1952)
Moon, J., Moser L.: On hamiltonian bipartite graphs. Israel J. Math1, 163–165 (1963)
Ore, O.: Note on hamiltonian circuits. Amer. Math Monthly67, 55 (1960)
Author information
Authors and Affiliations
Additional information
Research Supported by N.S.A. grant # MDA 904-94-H-2060 and NSF ND-EPSCoR # 4963.
Research Supported by O.N.R. grant # N00014-J-91-1085 and NSA grant # MDA 904-90-H-4034.
Research Supported by O.N.R. grant # N00014-J-91-1085.
Research Supported by O.N.R. grant # N00014-J-91-1098.
Research Supported by O.N.R. grant # N00014-J-93-1-0050.
Rights and permissions
About this article
Cite this article
Chen, G., Faudree, R.J., Gould, R.J. et al. Hamiltonicity in balancedk-partite graphs. Graphs and Combinatorics 11, 221–231 (1995). https://doi.org/10.1007/BF01793008
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01793008