On the 1-fault hamiltonicity for graphs satisfying Oreʼs theorem

Consider any undirected and simple graph G=(V,E)G=(V,E), where V denotes the vertex set and E the edge set of G. G is called hamiltonian if it contains a cycle that visits each vertex of G exactly once. It is proved by Ore that G   is hamiltonian if degG(u)+degG(v)⩾ndegG(u)+degG(v)⩾n holds for every nonadjacent pair of vertices u and v in V, where n is the total number of distinct vertices of G  . In this paper, we prove that in fact G−{x}G−{x} is hamiltonian for any x∈Vx∈V, unless G   belongs to one of the two exceptional families of graphs, denoted by G1G1 and G2G2. Moreover, G−{e}G−{e} is hamiltonian for any e∈Ee∈E, unless G   is one of the two particular types of graphs in G1G1.

► We establish a degree-based, sufficient condition for any graph G=(V,E)G=(V,E) to be 1-fault tolerant hamiltonian.
► We prove that almost all graphs satisfying Oreʼs theorem are 1-fault tolerant hamiltonian.
► We describe the only two exceptional graph families that satisfy Oreʼs condition but fail to be 1-fault tolerant hamiltonian.