JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]


Journal of Information Science and Engineering, Vol. 38 No. 4, pp. 833-857


On the 2-Vertex-Fault Hamiltonicity for Graphs Satisfying Ore's Theorem


HSIU-CHUNJ PAN1, HSUN SU2 AND SHIN-SHIN KAO1,+
1Department of Applied Mathematics
Chung Yuan Christian University
Taoyuan City, 320314 Taiwan

2Department of Public Finance and Taxation
Takming University of Science and Technology
Taipei, 11451 Taiwan
E-mail: shin2kao@gmail.com


Any undirected and simple graph G = (V, E), where V and E denote the vertex set and the edge set of G, is called Hamiltonian if it contains a cycle that visits each vertex of G exactly once. Ore proved that G is Hamiltonian if degG(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. Su, Shih, and Kao proved that any graph G satisfying Ore’s condition remains Hamiltonian after remov-ing any one vertex x € V unless G belongs to one of two exceptional families of graphs. This paper proves that G − {x, y} is Hamiltonian for any two vertices x, y € V, unless G belongs to one of the eight exceptional families of graphs, denoted by i, where i € {1, …, 8}.


Keywords: degree, Ore’s condition, Hamiltonian, 1-vertex fault Hamiltonian, 2-vertex fault Hamiltonian

  Retrieve PDF document (JISE_202204_09.pdf)