ON GRAPHS SATISFYING A LOCAL ORE-TYPE CONDITION

For an integer i, a graph is called an L(1)-graph if, for each triple of vertices u, v, w with d(u, v) = 2 and w is an element of N(u) boole an AND N(v), d(u) + d(v) greater than or equal to \N(u) boolean OR N(v ) boolean OR N(w)\ - i. Asratian and Khachatrian proved that connected L(0)-graphs of order at least 3 are hamiltonian, thus improving Ore's Theorem. All K-1,K-3-free graphs are L(1)-graphs, whence recognizing hamiltonian L(1)-graphs is an NP-complete problem. The following resul ts about L(1)-graphs, unifying known results of Ore-type and known res ults on K-1,K-3-free graphs, are obtained. Set K = {G\K-p,K-p+1 subset of or equal to G subset of or equal to K-p V <(K-p+1) <over bar> for some p greater than or equal to 2} (v denotes join). If G is a 2-conne cted L(1)-graph, then G is 1-tough unless G is an element of K. Furthe rmore, if G is a connected L(1)-graph of order at least 3 such that \N (u) boolean AND N(v)\ greater than or equal to 2 for every pair of ver tices u, v with d(u, v) = 2; then G is hamiltonian unless G is an elem ent of K, and every pair of vertices x, y with d(x, y) greater than or equal to 3 is connected by a Hamilton path. This result implies that of Asratian and Khachatrian. Finally, if G is a connected L(1)-graph o f even order, then G has a perfect matching. (C) 1996 John Wiley & Son s, Inc.