On the 1-fault hamiltonicity for graphs satisfying Ore's theorem and its generalization

Abstract

Consider any undirected and simple graph G=(V, E), where V and E denote the vertex set and the edge set of G, respectively. Let |G|=|V|=n. The well-known Ore's theorem states that if deg_G(u)+deg_G(v)≥n+k holds for each pair of nonadjacent vertices u and v of G, then G is traceable for k=−1, hamiltonian for k=0, and hamiltonian-connected for k=1. Lin et al. generalized Ore's theorem and showed that under the same condition as above, G is r*-connected for 1≤r≤k+2 with k≥1. In this paper, we improve both theorems by showing that the hamiltonicity or r*-connectivity of any graph G satisfying the condition deg_G(u)+deg_G(v)≥n+k with k≥−1 is preserved even after one vertex or one edge is removed, unless G belongs to two exceptional families.

Keywords:

• degree
• hamiltonian
• 1-fault hamiltonian
• Ore theorem

2010 AMS Subject Classifications:

• 68R05
• 68R10
• 90C27
• 94C15

Acknowledgements

This work was supported by National Science Council, National Taiwan University and Intel Corporation under Grants NSC101-2911-I-002-001 and NTU102R7501. This work was supported in part by National Science Council of the Republic of China under Contract NSC102-2115-M-033 -004 -. Correspondence to: Professor S.-S. Kao, e-mail: [email protected].