Notes on vertex pancyclicity of graphs
In (2012) [7], Kewen Zhao and Yue Lin introduced a new sufficient condition for pancyclic graphs and proved that if G is a 2-connected graph of order n >= 6 with vertical bar N(x) boolean OR N(Y)vertical bar + d(w) >= n for any three vertices x, y, w of d(x, y) = 2 and wx or wy is not an element of (G), then G is 4-vertex pancyclic or G belongs to two classes of well-structured exceptional graphs. This result generalized the two results of Bondy in 1971 and Xu in 2001. In this paper, we first prove that if G is a 2-connected graph of order n >= 6 with vertical bar N(x) boolean OR N(Y)vertical bar + d(w) >= n for any three vertices x, y, w of d(x, y) = 2 and wx or wy is not an element of E(G), then each vertex u of G with d(u) >= 3 is 5-pancyclic or G = K-n/2,K-n/2, and we also show that our result is best possible. On the basis of this result, we prove that there exist at least two pancyclic vertices in G or G = K-n/2,K-n/2. In addition, we give a new proof of a result in Cai (1984) [2]. (C) 2013 Elsevier B.V. All rights reserved.
pancyclicity 2-connected graphs combinatorial problems vertex-pancyclicity