Almost Hamiltonian Cubic Graphs
Narong Punnim, Varaporn Saenpholphat, Sermsri Thaithae · 2007
A Hamiltonian walk in a connected graph G of order n is a closed spanning walk of minimum length in G. For a connected graph G, let h(G) be the length of a Hamiltonian walk in G and call it the Hamiltonian number of G. Let i be a non-negative integer. A connected graph G of order n is called an i-Hamiltonian if h(G) = n+i. Thus a 0-Hamiltonian graph is Hamiltonian. A 1-Hamiltonian graph is called an almost Hamiltonian graph. We prove in this paper that for an even integer n ≥ 10 there exists an almost Hamiltonian cubic graph of order n. Let P(k, m) be the generalized Petersen graph of order 2k. We show that P(k, m) is an almost Hamiltonian graph if and only if m = 2 and k ≡ 5(mod 6). For a cubic graph G, we define G * to be the graph obtained from G by replacing each vertex of G to a triangle, matching the vertices of the triangle to the former neighbors of the replaced vertex. We show that G is Hamiltonian if and only if G * is Hamiltonian and if G is almost Hamiltonian then G * is 2-Hamiltonian. Key words: Hamiltonian walk, Hamiltonian number, and cubic graph.