| 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. |
