A Hamiltonian walk in a graph G is a closed spanning walk of minimumlength. 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 he(G) It has been shown in [6] that for every graph G of order n, h c ( G ) < 2 n - 2 2 n - 2 < 2, and hc(G) = — if and only if G is a tree. Let CR.(3n) be the class of connected cubic graphs of order n. By putting h(3") {h(G) : G E CR(3")}, 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 connectedcubic graphs as follows. For an even integer n > 4 and n 4. There exists an integer b such that h(3") = {k EZ:n 0, then b = 18 + 3i.
展开▼
