Premium
On graphs satisfying a local ore‐type condition
Author(s) -
Asratian A. S.,
Broersma H. J.,
Van den Heuvel J.,
Veldman H. J.
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199601)21:1<1::aid-jgt1>3.0.co;2-w
Subject(s) - combinatorics , mathematics , graph , discrete mathematics , hamiltonian path
Abstract For an integer i, a graph is called an L i ‐graph if, for each triple of vertices u, v, w with d ( u, v ) = 2 and w (element of) N ( u ) (intersection) N ( v ), d ( u ) + d ( v ) ≥ | N ( u ) (union) N ( v ) (union) N ( w )| — i. Asratian and Khachatrian proved that connected L o ‐graphs of order at least 3 are hamiltonian, thus improving Ore's Theorem. All K 1,3 ‐free graphs are L 1 ‐graphs, whence recognizing hamiltonian L 1 ‐graphs is an NP‐complete problem. The following results about L 1 ‐graphs, unifying known results of Ore‐type and known results on K 1,3 ‐free graphs, are obtained. Set K = lcub;G|K p,p+1 (contained within) G (contained within) K p V K p+1 for some ρ ≥ } (v denotes join). If G is a 2‐connected L 1 ‐graph, then G is 1‐tough unless G (element of) K . Furthermore, if G is as connected L 1 ‐graph of order at least 3 such that | N ( u ) (intersection) N ( v )| ≥ 2 for every pair of vertices u, v with d ( u, v ) = 2, then G is hamiltonian unless G ϵ K , and every pair of vertices x, y with d ( x, y ) ≥ 3 is connected by a Hamilton path. This result implies that of Asratian and Khachatrian. Finally, if G is a connected L 1 ‐graph of even order, then G has a perfect matching. © 1996 John Wiley & Sons, Inc.