Minimum k‐hamiltonian graphs, II

Abstract

We consider in this paper graphs which remain hamiltonian after the removal of k edges (k‐edge hamiltonian) or k vertices (k‐hamiltonian). These classes of graphs arise from reliability considerations in network design. In a previous paper, W. W. Wong and C. K. Wong presented families of minimum k‐hamiltonian graphs and minimum k‐edge hamiltonian graphs for k even. Here, we complete this study in the case where k is odd. Copyright © 1986 Wiley Periodicals, Inc., A Wiley Company