A method in graph theory |
| |
Authors: | J.A. Bondy V. Chvatal |
| |
Affiliation: | Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ont., Canada;Centre de recherches mathématiques, Université de Montréal, Montréal, P.Q., Canada |
| |
Abstract: | A unified approach to a variety of graph-theoretic problems is introduced. The k-closure Ck(G) of a simple graph G of order n is the graph obtained from G by recursively joining pairs of nonadjacent vertices with degree-sum at least k. It is shown that, for many properties P, one can find a suitable value of k (depending on P and n) such that if Ck(G) has P, then so does G. For instance, if P is the hamiltonian property, one may take k = n. Thus if Cn(G) is hamiltonian, then so is G; in particular, if n ? 3 and Cn(G) is complete, then G is hamiltonian. This condition for a graph to be hamiltonian is shown to imply the well-known conditions of Chvátal and Las Vergnas. The same method, applied to other properties, yields many new theorems of a similar nature. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|