Construction Scheme

Applying Theorem 3, we can easily obtain other optimal k-hamiltonian graphs from some known k-hamiltonian graph by (k+2)-node expansion on a vertex of degree k+2. It is known that the clique K_k+3 is the smallest optimal k-hamiltonian graphs. Since K_k+3 is (k+2)-regular, the graphs obtained by a sequence of (k+2)-node expansion from K_k+3 are also (k+2)-regular, and thus optimal k-hamiltonian. One possible sequence of (k+2)-node expansion is described in the following algorithm.

¡@¡@ALGORITHM Bell(k+2,s)
¡@¡@¡@ $G \leftarrow K_{k+3}$
¡@¡@¡@¡@¡@pick any vertex r as the root of G
¡@¡@¡@¡@¡@for $i \leftarrow 1$ to s-1 do
¡@¡@¡@¡@¡@¡@ $B \leftarrow \{v \mid distance(v, r) = i \}$
¡@¡@¡@¡@¡@¡@¡@for all $v \in B$
¡@¡@¡@¡@¡@¡@¡@¡@¡@ $G \leftarrow EXP_{k+2}(G,v)$

Let B(k, s) denote the optimal k-hamiltonian graph obtained by Bell(k+2, s). The graphs B(1, 1), B(1, 2), and B(1, 3) are shown in Figure 2. The node labeled with r indicates the root assigned by Bell(k+2, s). It can be verified that the number of nodes in B(k,s) is $\frac{(k+2)(k+1)^s -2}{k}$. Moreover, the distance between a node v to the root r is at most s. Thus, the diameter of B(k,s) is at most 2s. In other words, we have constructed a family of optimal k-hamiltonian graphs with diameter $2 \log_{k+1} n - O(1)$, that is 2 times of Moore bound. We thus have the following theorem.

Theorem 6

The graph B(k, s) is an optimal k-hamiltonian graph having diameter $2 \log_{k+1} n - O(1)$, where n is the number of vertices in B(k,s).

  

Figure 2: The graphs B(1, 1), B(1, 2), and B(1, 3)