THE HAMILTONIAN NUMBER OF SOME CLASSES OF CUBIC GRAPHS

Abstract

A Hamiltonian walk in a graph G is a closed spanning walk of minimum length. The length of a Hamiltonian walk in G will be denoted by h(G). Thus if G is a connected graph of order n ≥ 3, then h(G)=n if and only if G is Hamiltonian. Thus h may be considered as a measure of how far a given graph is from being Hamiltonian. Let G be a connected graph of order n. The Hamiltonian coefficient of G, denoted by hc(G), is defined as hc(G)=h(G) n . It has been shown in [6] that for every graph G of order n, hc(G) ≤ 2n−2 n < 2, and hc(G)=2n−2 n if and only if G is a tree. Let CR(3n) be the class of connected cubic graphs of order n. By putting h(3n)={h(G):G ∈CR(3n)}, we obtained in [10] that if G is a 2-connected cubic graph of order n ≥ 10 and h(G) ≥ n + 2, then there exists a connected cubic graph G of order n containing a cut edge such that h(G) ≤ h(G). We obtained in the same paper concerning the results on Hamiltonian number in the class of connected cubic graphs as follows. For an even integer n ≥ 4 andn = 14. There exists an integer b such that h(3n)={k ∈ Z : n ≤ k ≤ b}. Moreover, an explicit formula for the integer b is given by the following.
1. b = n if and only if n =4 ,6,8. 2. b = n + 2 if and only ifn = 10 ,12.
3. If n = 14 + 2 i and i ≥ 0, then b = 18 + 3 i.