Introduction and Definitions

Let G = (V, E) be an undirected graph. A hamiltonian cycle of G is a cycle that traverses every node of G exactly once. Graph G is called a hamiltonian graph if it contains a hamiltonian cycle. The graph G - v is a sub-graph of G obtained by removing v and all of edges incident at v from G. Graph G - e denotes the sub-graph of G with e deleted. Let k be a positive integer and F be a subset of $V \cup E$ with $\vert F\vert \le k$. The graph G - F is the sub-graph that is deleted all edges and nodes in F from G. The graph G is k-hamiltonian if the graph G - F is a hamiltonian graph. An n-node k-hamiltonian graph is optimal if it contains the fewest number of edges among all n-node k-hamiltonian graphs. A k-node-hamiltonian graph is a special case of k-hamiltonian graph in which the faulty set F is restricted to $F \subset V$. Similarly, a k-hamiltonian graph is called k-edge-hamiltonian if $F \subset E$.

Previous research on optimal k-hamiltonian graphs were mainly focused on k = 1. Mukhopadhyaya and Sinha [6] and Harary and Hayes [3,4] presented families of optimal 1-hamiltonian graphs. Wang et al. [12] constructed a family of optimal n-node 1-hamiltonian graphs for all even n. For k > 1, we can only find one family of optimal k-hamiltonian graphs for k = 2 or 3. Paoli et al. [8] and Wong and Wong [13] proposed a family of graphs, denoted by G(n, k), for $k \ge 1$ which were shown to be both optimal k-node-hamiltonian and optimal k-edge-hamiltonian for n even and for n odd, respectively, in [8] and [13]. Though G(n,k) is both optimal k-node-hamiltonian and optimal k-edge-hamiltonian for $k \ge 2$, it does not imply that G(n,k) is optimal k-hamiltonian. Sung et al. [10] showed that G(n,k) is optimal k-hamiltonian for k =2,3 and conjectured that G(n,k) is optimal k-hamiltonian for all $k \ge 1$.

The diameter of a graph is the maximum distance among all pairs of nodes. A network with smaller diameter can yield shorter communication delay. Now we compare the diameter of the aforementioned optimal 1-hamiltonian graphs. The graphs presented by Mukhopadhyaya and Sinha [6] have the diameter $\lfloor\frac{n}{6}\rfloor + 2$ for n even, and $\lfloor\frac{n}{8}\rfloor + 3$ for n odd. The graphs proposed by Harary and Hayes [3,4] and by Wang et al. [12] have diameter of $\lfloor\frac{n + 1} {4} \rfloor$ and $O(\sqrt{n})$, respectively. The diameter of G(n,k) is O(n) if k is considered as a constant. Can we find optimal k-hamiltonian graphs with smaller diameter? This problem is related to the famous (n, d, D) problem in which we want to construct a graph of n nodes with maximum degree d such that the diameter D is minimized. When d and n are given, the lower bound on diameter D, called the Moore bound, is given by $D \ge \log_{d - 1} n - \frac{2}{d}$ [2].

In this paper, we introduce a node operation and incorporate it in a general scheme to construct optimal k-hamiltonian graphs. Applying this scheme, we construct a family of optimal k-hamiltonian graphs for all $k \ge 1$ with diameter $2 \log_{d-1} n - O(1)$, i.e., 2 times of Moore bound.

The rest of this paper is organized as follows. In section 2 we discuss the fault-tolerance properties of complete graphs. Section 3 introduces the general construct scheme, p-node expansion, for optimal k-hamiltonian graphs. We will use this scheme to construct a family of optimal k-hamiltonian graph in section 4. A conclusion is given in section 5.