ISSN:
1435-5914
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract Asratian and Khachatrian proved that a connected graphG of order at least 3 is hamiltonian ifd(u) + d(v) ≥ |N(u) ∪ N(v) ∪ N(w)| for any pathuwv withuv ∉ E(G), whereN(x) is the neighborhood of a vertexx. We prove that a graphG with this condition, which is not complete bipartite, has the following properties: a) For each pair of verticesx, y with distanced(x, y) ≥ 3 and for each integern, d(x, y) ≤ n ≤ |V(G)| − 1, there is anx − y path of lengthn. (b) For each edgee which does not lie on a triangle and for eachn, 4 ≤ n ≤ |V(G)|, there is a cycle of lengthn containinge. (c) Each vertex ofG lies on a cycle of every length from 4 to |V(G)|. This implies thatG is vertex pancyclic if and only if each vertex ofG lies on a triangle.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01858455
Permalink