International Journal of Mathematics and Mathematical Sciences
Volume 24 (2000), Issue 10, Pages 691-697
doi:10.1155/S0161171200003653
Long cycles in certain graphs of large degree
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.
Abstract
Let G be a connected graph of order n and
X={x∈V: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.