Some panconnected and pancyclic properties of graphs with a local ore-type condition

Autor: G. V. Sarkisian, Armen S. Asratian
Rok vydání: 1996
Předmět:
Zdroj: Graphs and Combinatorics. 12:209-219
ISSN: 1435-5914
0911-0119
DOI: 10.1007/bf01858455
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: