International Journal of Mathematics and Mathematical Sciences
Volume 24 (2000), Issue 10, Pages 691-697

Long cycles in certain graphs of large degree

Pak-Ken Wong

Department of Mathematics and Computer Science, Seton Hall University, South Orange 07079, NJ, USA

Received 20 March 1998

Copyright © 2000 Pak-Ken Wong. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


Let G be a connected graph of order n and X={xV:d(x)n/2}. Suppose |X|3 and G satisfies the modified Fan's condition. We show that the vertices of the block B of G containing X form a cycle. This generalizes a result of Fan. We also give an efficient algorithm to obtain such a cycle. The complexity of this algorithm is O(n2). In case G is 2-connected, the condition |X|3 can be removed and G is hamiltonian.