Minimum K‐hamiltonian graphs

Abstract

We consider two new classes of graphs arising from reliability considerations in network design. We want to construct graphs with a minimum number of edges which remain Hamiltonian after k edges (or k vertices) have been removed. A simple construction is presented for the case when k is even. We show that it is minimum k‐edge Hamiltonian. On the other hand, Chartrand and Kapoor previously proved that this class of graphs was also minimum k‐vertex Hamiltonian. The case when k is large (odd or even) is also considered. Some results about directed graphs are also presented. Copyright © 1984 Wiley Periodicals, Inc., A Wiley Company