A vertex subsetX of a graphG is said to be cyclable inG if there is a cycle inG containing all vertices ofX. Ore [6] showed that the vertex set ofG with cardinalityn ≥ 3 is cyclable (i.e.G is hamiltonian) if the degree sum of any pair of nonadjacent vertices inG is at leastn. Shi [8] and Ota [7] respectively generalized Ore’s result by considering the cyclability of any vertex subsetX ofG under Ore type condition. Flandrinetal. [4] in 2005 extended Shi’s conclusion under the condition calledregionalOre′scondition. Zhu, Li and Deng [10] introduced the definition of implicit degrees of vertices. In this work, we generalize the result of Flandrinetal. under their type condition with implicit degree sums. More precisely, we obtain thatX is cyclable in ak-connected graphG if the implicit degree sum of any pair of nonadjacent verticesu,v ∈ X_i is at least the order ofG, where eachX_i,i = 1,2, ⋯ ,k is a vertex subset ofG andX = ∪ ^k_i = 1X_i. In [10], the authors demonstrated that the implicit degree of a vertex is at least the degree of the vertex. Hence our result is better than the result of Flandrinetal. in some way.

Unable to display preview. Download preview PDF.

Authors and Affiliations

1. School of Mathematics and Statistics, Lanzhou University, Lanzhou, 730000, China

   Hao Li, Wantao Ning & Junqing Cai

2. L R I, UMR 8623 CNRS and Université de Paris-Sud 11, F-91405, Orsay, France

   Hao Li

Editors and Affiliations

1. Department of Computer Science, Purdue University, 305 North University Street, 47907, West Lafayette, IN, USA

   Mikhail Atallah

2. Department of Computer Science, Illinois Institute of Technology, 60616, Chicago, IL, USA

   Xiang-Yang Li

3. Department of Computer Science, Montana State University, EPS 357, 59717, Bozeman, MT, USA

   Binhai Zhu

Reprints and permissions

© 2011 Springer-Verlag Berlin Heidelberg

Policies and ethics