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 degG(u)+degG(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 degG(u)+degG(v)≥n+k with k≥−1 is preserved even after one vertex or one edge is removed, unless G belongs to two exceptional families.
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].