On graphs satisfying a local ore‐type condition

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.