Node Expansion

Let x be a vertex of G=(V,E) with deg_G(x) = k + 2. Let $x_1, x_2, \ldots, x_{k+2}$ denote all of the vertices adjacent to x and $E_G(x) = \{(x, x_i)\vert 1 \le i \le k+2\}$. Let Z_x = (Y_x, W_x) be a (k+2)-node clique with vertex set $Y_x = \{y_{x_1}, y_{x_2}, \ldots, y_{x_{k+2}}\}$ and edge set $W_x = \{(y_{x_i}, y_{x_j}) \vert i \neq j, \forall y_{x_i}, y_{x_j} \in Y_x \}$. Let $E(G, x) = Y_x \cup W_x \cup \{(x_i, y_{x_i}) \vert 1 \le i \le k+2\}$. The node expansion of G on x, denoted by EXP(G, x), is a graph that is obtained from G by replacing x with the clique Z_x. To be specific, the graph EXP(G, x) = (V^*, E^*) has the vertex set $V^*= (V - \{x\}) \cup Y_x$ and edge set $E^*= E \cup W_x \cup \{(x_i, y_{x_i}) \vert 1 \le i \le k+2 \} - \{(x, x_i) \mid 1 \le i \le k+2\}$. The node expansion is degree preserving, that is, deg_{EXP(G, x)}(y_xi) = deg_G(x) = k+2 for all $y_{x_i} \in Y_x$ and deg_{EXP (G, x)}(x_j) = deg_G(x_j) for all $x_j \in (V - \{x\})$. In particular, if G is (k+2)-regular, EXP(G, x) is also (k+2)-regular. The graphs K₅ and EXP (K₅, x) are illustrated in Figure 1.

Lemma 2

  Let t be any integer for $0 \le t \le k$. Given $F_1 \subset ((V - \{x\}) \cup (E - E_G(x)))$. If $G - (F_1 \cup F_2)$ is hamiltonian where F₂ is an arbitrary set of E_G(x) and |F₂| = t, then the graph $EXP(G, x) - (F_1 \cup F_3)$ is hamiltonian, where $F_3 \subset E(G, x)$ and |F₃| = t.

Proof: $\;$ Applying Theorem 1, we can obtain that the graph Z_x - F₃ is (k+2-t)-HP. That is, there exists a set $X \subset Y_x$ of size k+2-t such that every two distinct nodes in X can be joined by a hamiltonian path of the graph Z_x - F₃. We define a faulty set $F_2^{\prime}$ of G as follows:

$$F_2^{\prime} = \{(x, x_i) \mid \forall y_{x_i} \notin X\}.$$

Thus, $\vert F_2^{\prime}\vert = \vert Y_x\vert - \vert X\vert = k + 2 - (k+2 - t) = t$ and $F_2^{\prime} \subset E_G(x)$. The graph $G - (F_1 \cup F_2^{\prime})$ is hamiltonian since $G - (F_1 \cup F_2)$ is hamiltonian for all $F_2 \subset E_G(x)$ and |F₂| = t. Thus, there is a hamiltonian cycle $C = \langle x_i, x, x_j \rightarrow P \rightarrow x_i \rangle$ in the graph $G - (F_1 \cup F_2^{\prime})$ where P is a path from x_j to x_i. By the definition of $F_2^{\prime}$, y_xi and y_xj are both in X. Hence, there exists a hamiltonian path Q joining y_xi and y_xj in the graph Z_x - F₃. Therefore, $\langle x_i, y_{x_i} \rightarrow Q \rightarrow y_{x_j}, x_j \rightarrow P \rightarrow x_i \rangle$ forms a hamiltonian cycle in the graph $EXP(G, x) - (F_1 \cup F_3)$. This lemma is proved. $\Box$

  

Figure 1: The graph K₅ and EXP₄(K₅, x).

Theorem 2

  Let x be a vertex of G=(V,E) with deg_G(x)= k+2. If G is k-hamiltonian, then EXP(G, x)=(V^*, E^*) is also k-hamiltonian.

Proof: $\;$ Let F be an arbitrary faulty set of the graph EXP(G, x) where $\vert F\vert \le k$. Let $F_1 = F \cap (G - E_G(x) - \{x\})$ and F₃ = F - F₁. Since G is k-hamiltonian, for every $F_2 \subset E_G(x)$ where |F₂| = |F| - |F₁| = |F₃|, the graph $G - (F_1 \cup F_2)$ is hamiltonian. Applying Lemma 2, we can obtain that the graph $EXP(G, x) - (F_1 \cup F_3)$ is hamiltonian. Therefore, EXP(G, x) is k-hamiltonian. The theorem is proved. $\Box$

Theorem 3

  Let G = (V,E) be a graph of n vertices. Let x and y be two distinct vertices in G where deg_G(x)=k+2 and $k+2 \le deg_G (y) \le k+3$. If G is optimal k-hamiltonian and G - y is (k+2)-regular, EXP(G, x) = (V^*, E^*) is optimal k-hamiltonian.

Proof: $\;$ If G is k-hamiltonian, it follows from Theorem 2 that EXP(G, x) is k-hamiltonian. If deg_G(y) = k+2, G is regular since G -y is (k+2)-regular. Thus EXP(G, x) is (k+2)-regular and optimal k-hamiltonian. If deg_G(y) = k+3, it follows that both k and n are odd. Therefore |V^*| = n +k+1 is also odd. Since (k+2)-node expansion is degree preserving, deg_{EXP(G, x)}(y) = deg_G(y) = k+3 and deg_{EXP(G, x)}(v) = k+2 for all $v \in V^* - \{y\}$. Therefore, EXP(G, x) is optimal k-hamiltonian. $\Box$

Applying Theorem 3, we can obtain other optimal k-hamiltonian graphs from some known optimal k-hamiltonian graphs by (k+2)-node expansion. Moreover, we give the following conjecture. If this conjecture is true , we can obtain other optimal k-hamiltonian graphs from every known optimal k-hamiltonian graphs by (k+2)-node expansion.

Conjecture 1

Let G = (V, E) be an optimal k-hamiltonian graph and |V| = n. The graph G is (k+2)-regular if n or k is even, or exactly 2one node of G has degree k + 3 if both k and n are odd, for all $k \ge 1$ and n > k + 1.

The node expansion of G=(V, E) on the set $X \subset V$, denoted by EXP(G, X), is a graph that is obtained from G by a sequence node-expansion operations on every node $x \in X$.

Lemma 3

  If the graph G = (V, E) is (k+2)-regular and k-edge-hamiltonian, then the graph EXP(G, X) - F is hamiltonian for every $F \subset ((E - (\bigcup_{x \in X}E_G(x))) cup (\bigcup_{x \in X}E(G, x)))$ for $X \subseteq V$ and $\vert F\vert \le k$.

Proof: $\;$ Let $X^{\prime} \subset (V - \{v\})$ and $X = X^{\prime} \cup \{v\}$. Assume that the graph $EXP(G, X^{\prime}) - F^{\prime}$ is hamiltonian for every $F^{\prime} \subset ((E - \bigcup_{x \in X^{\prime}}E_G(x)) \bigcup_{x \in X^{\prime}}E(G, x))$ for $\vert F^{\prime}\vert \le k$. Let F be a subset of $(E - \bigcup_{x \in X}E_G(x)) \bigcup_{x \in X}E(G, x)$ and $\vert F\vert \le k$. Let $F_1 = F \cap (EXP(G, X) - E(EXP(G, X^{\prime}), v))$ and F₃ = F - F₁ and F₂ be an arbitrary subset of $E_{EXP(G, X^{\prime})}(v)$ with |F₂| = |F₃|. Therefore, the graph $EXP(G, X^{\prime}) - (F_1 \cup F_2)$ is hamiltonian since $(F_1 \cup F_2)$ is a subset of $((E - \bigcup_{x \in X^{\prime}}E_G(x)) \bigcup_{x \in X^{\prime}}E(G, x))$ and $\vert F_1 \cup F_2\vert = \vert F\vert \le k$. Applying Lemma 2, we can obtain that the graph $EXP(G, X) - (F_1 \cup F_3)$ is hamiltonian. Since $F = F_1 \cup F_3$ is an arbitrary subset of $(E - \bigcup_{x \in X}E_G(x)) \bigcup_{x \in X}E(G, x)$ and $\vert F\vert \le k$, this lemma is proved. $\Box$

Theorem 4

  If the graph G = (V, E) is (k+2)-regular and optimal k-edge-hamiltonian, then the graph EXP(G, V) = (V^*, E^*) is (k+2)-regular and optimal k-hamiltonian.

Proof: $\;$Applying Lemma 3, we can obtain that the graph EXP(G, V) - F is hamiltonian for every $F \subset ((E - \bigcup_{x \in V}E_G(x)) \bigcup_{x \in V}E(G, x))$ for $\vert F\vert \le k$. In fact, $(E - \bigcup_{x \in V}E_G(x)) \bigcup_{x \in V}E(G, x) = V^* \cup E^*$. Therefore, EXP(G, V) is k-hamiltonian. This theorem is proved. $\Box$

It is known that hypercube, denoted by Q(n), is an n-regular, node symmetric, and link symmetric graph with diameter n. Moreover, Q(n) is shown to be (n-2)-edge hamiltonian graph in [1,9]. We can obtain Corollary 2 applying Theorem 4.

Corollary 2

  Let Q(n) = (V, E)8 be an n-dimensional hypercube. The graph EXP(Q(n), V) is an optimal (n-2)-hamiltonian and node symmetric graph with $n \cdot 2^n$ vertices, degree n, and diameter 2n.

The star graph, denoted by S(n), is also a famous interconnection network. It is (n-1)-regular, node symmetric and edge symmetric graph whose vertex number is n! and diameter is $\lfloor 3(n-1)/2\rfloor$. In [11], the authors show that S(n) is an (n-3)-edge hamiltonian graph. Applying Theorem 4, we also can obtain Corollary 3.

Corollary 3

  Let S(n) = (V, E) be an n-dimensional star graph. The graph EXP(S(n), V) is an optimal (n-3)-hamiltonian and node symmetric graph with $n \cdot n!$ vertices, degree (n-1), and diameter $2 \lfloor 3(n - 1)/2 \rfloor$.

Let d(u, v) denote the distance of vertices u and v.

Lemma 4

  Let G = (V, E) be a (k+2)-regular and optimal k-hamiltonian graph. There exists a hamiltonian path P(u, v) if $u, v \in V$ and the distance $d(u, v) \le 2$.

Proof: Case 1: d(u, v) = 1.

Let $x_1, x_2, \ldots, x_k, x_{k+1}, v$ be the neighbors of u and $F = \{(x_i, u)\vert 1 \le i \le k\}$. Since G is k-hamiltonian, the graph G - F contains a hamiltonian cycle H which cover the edge (u, v). Thus, there exists a hamiltonian path P(u, v) = H - (u, v).

Case 2: d(u, v) = 2.

Let w be a vertex of G and (u, w), (w, v) be two edges of G. The neighbors of w are $x_1, x_2, \ldots, x_k, u, v$. Let $F = \{u, (w, x_1), (w, x_2), \ldots, (w, x_{k-1})\}$ be the faulty set. Since G is k-hamiltonian, the graph G - F contains a hamiltonian cycle H which cover the edge (w, v). Thus, there exists a hamiltonian path P(u, v) = H - (w, v) + (u, w). $\Box$

Let G = (V, E) be a graph. The graph $G \times K_2$ is the cartesian product of the graphs G and K₂. The vertex set $V(G \times K_2)$ is $\{(v, i)\vert \forall v \in V$ and $i = 1, 2 \}$. The edge set $E(G \times K_2)$ is $\{((u, i), (v, j)) \vert$ if $(u, v) \in E, i = j$ or $u = v, i \neq j \}$. The degree of $(v, i) \in (G \times K_2)$ equal the degree of $v \in G$ plus 1. Let G_i be a sub-graph of $G \times K_2$ and G_i isomorphic to G. To be specific, the vertex set of G_i is $\{(v, i) \vert \forall v \in V \}$ and the edge set of G_i is $\{((u, i), (v, i)) \vert \forall (u, v) \in E \}$.

Theorem 5

  Let G = (V, E) be a (k+2)-regular and k-hamiltonian graph. The graph $G \times K_2$ is a (k+3)-regular and (k+1)-hamiltonian graph.

Proof: Since the degree of $(v, i) \in (G \times K_2)$ equal the degree of $v \in G$ plus 1, $G \times K_2$ is (k+3)-regular. We will prove that $(G \times K_2) - F$ is a hamiltonian graph in which $F \subset (V(G \times K_2) \cup E(G \times K_2))$ and |F| = k + 1. We prove this theorem by the following two cases.

Case 1: The faulty set F is included in the sub-graph G_i for i = 1, 2.

Let f be a fault of F. Since G_i is a k-hamiltonian graph, $G_i - (F - \{f\})$ contains a hamiltonian cycle H. Thus G_i - F contains a hamiltonian path $H - \{f\} = HP((u, i), (v, i))$, in which $(u, i), (v, i) \in V(G_i)$ are end vertices. If f is an edge, d((u, i), (v, i)) = 1. Otherwise f is a vertex and $d((u, i), (v, i)) \le 2$. Also, the distance $d((u, j), (v, j)) \le 2$ if $i \neq j$. Applying Lemma 4, we can obtain that there exists a hamiltonian path HP((u, j), (v, j)) between (u, j) and (v, j) in G_j. Therefore, we can construct a hamiltonian cycle $HC = \langle (u, i) \rightarrow HP((u, i), (v, i)) \rightarrow (v, i), (v, j) \rightarrow HP((v, j), (u, j)) \rightarrow (u, j), (u, i) \rangle$ of $(G \times K_2) - F$.

Case 2: The faulty set F is not included in the sub-graph G_i for i = 1, 2.

Since the faults are not all in G_i, the number of faults in G_i is less than or equal to k.Let $f_i = \vert F \cap (\{(v, i) \vert \forall v \in V \} \cup \{((u, i), (v, i)) \vert \forall (u, v) \in E \})\vert$, $f_j = \vert F \cap (\{(v, j) \vert \forall v \in V \} \cup \{((u, j), (v, j)) \vert \forall (u, v) \in E \})\vert$ and $f_c = \vert F \cap \{((u, i), (u, j)) \vert \forall u \in V$ and $i \neq j\}\vert$. Thus f_i + f_j + f_c = k + 1. Let $(x, i) \in V(G_i)$ and $(v_1, i), (v_2, i), \cdots, (v_{k+2}, i)$ be the neighbor of (x, i) and $((x, i), (x, j)) \not\in F$. Since G_i and G_j are k-hamiltonian, there exist k + 2 - f_i edges incident to (x, i) in some hamiltonian cycle in G_i and k + 2 - f_j edges incident to (x, j) in some hamiltonian cycle in G_j. Because (k+2-f_i) + (k+2-f_j) = 2k+4-f_i-f_j = k+3+f_c, there exist 1 + f_c vertices (v_ts, i) for $1 \le s \le 1+f_c$ where ((x, i), (v_ts, i)) and ((x, j), (v_ts, j)) are in some hamiltonian cycles of G_i and G_j, respectively. Therefore, there exists a vertex (v_r, i) for $((v_r, i), (v_r, j)) \not\in F$ where ((x, i), (v_r, i)) and ((x, j), (v_r, j)) are in some hamiltonian cycles HC_i and HC_j of G_i and G_j, respectively. Hence there exists a hamiltonian cycle $HC_i \cup HC_j \cup \{((x, i), (x, j)), ((v_r, i), (v_r, j)) \} - \{((x, i), (v_r, i)), ((x, j), (v_r, j))\}$ of $(G \times K_2) - F$.

This theorem is proved. $\Box$