Degree Sum Conditions for Hamiltonicity on k-Partite Graphs |
| |
Authors: | Guantao Chen Michael S Jacobson |
| |
Institution: | 1. Department of Mathematics and Computer Science, Georgia State University, Atlanta, GA, 30303, USA 2. Department of Mathematics, University of Louisville, Louisville, KY, 40292, USA
|
| |
Abstract: | One of the earliest results about hamiltonian graphs was given by Dirac. He showed that if a graph G has order p and minimum degree at least \(\frac{p} {2}\) then G is hamiltonian. Moon and Moser showed that if G is a balanced bipartite graph (the two partite sets have the same order) with minimum degree more than \(\frac{p} {4}\) then G is hamiltonian. Recently their idea is generalized to k-partite graphs by Chen, Faudree, Gould, Jacobson, and Lesniak in terms of minimum degrees. In this paper, we generalize this result in terms of degree sum and the following result is obtained: Let G be a balanced k-partite graph with order kn. If for every pair of nonadjacent vertices u and v which are in different parts $$d(u) + d(v) > \left\{ {\begin{array}{*{20}c} {\left( {k - \frac{2} {{k + 1}}} \right)n} & {if k is odd} \\ {\left( {k - \frac{4} {{k + 2}}} \right)n} & {if k is even} \\ \end{array} } \right.,$$ then G is hamiltonian. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|