Zbigniew R. Bogdanowicz

US Army, CCDC Armaments Center, Picatinny, New Jersey 07806, USA

A Hamiltonian graph G = (V, E) is called hyper-Hamiltonian if G − v is Hamiltonian for any v ∈ V (G). G is called a circulant if its automorphism group contains a |V (G)|-cycle. First, we give the necessary and sufficient conditions for any undirected connected circulant to be hyper-Hamiltonian. Second, we give necessary and sufficient conditions for a connected circulant digraph with two jumps to be hyper-Hamiltonian. In addition, we specify some sufficient conditions for a circulant digraph with arbitrary number of jumps to be hyper-Hamiltonian.

Keywords: Hyper-hamiltonian graph, Hamilton cycle, circulant, Hamiltonian graph

Mathematics Subject Classification: 05C38

DOI: 10.5614/ejgta.2021.9.1.16

1. Introduction

A Hamilton cycle in an undirected graph G = (V, E) is a cycle that passes through every vertex v ∈ V (G) exactly once. A graph G is called Hamiltonian if it contains such a cycle, and a Hamiltonian graph G is hyper-Hamiltonian if G − v is Hamiltonian for any v ∈ V (G). It is well known that the problem of determining whether or not an arbitrary graph contains a Hamilton cycle is NP-complete. This implies that the problem of determining if an arbitrary graph is hyper-Hamiltonian is at least as hard as NP-complete problems. For special families of graphs, however, a Hamilton cycle can be computed efficiently. In particular, it is known that a class of undirected vertex-symmetric graphs called circulants, considered in the third section of this paper, always contains a Hamilton cycle [7]. Furthermore, since all circulants (undirected and directed) are vertex-transitive then the condition for hyper-Hamiltonicity in these graphs has to be checked

Received: 8 June 2020, Revised: 13 February 2021, Accepted: 27 February 2021.

for only one vertex. Hence, circulants represent a family of graphs for which it is natural to consider if they are hyper-Hamiltonian. Other families of graphs with respect to hyper-Hamiltonian cycles have been also investigated in the literature, as this problem seems to be relevant to network survivability with respect to a single node failure [9]. For example, Araki examined hyper-Hamiltonian laceability of Cayley graphs, taking into consideration networks for parallel and distributed systems [1]. Mai et al. considered sufficient conditions for a hyper-Hamiltonian cycle in generalized Petersen graphs [8]. Del-Vecchio et al. also focused on some sufficient conditions for a graph to be hyper-Hamiltonian by providing spectral and non-spectral conditions for the hyper-Hamiltonian cycle [6]. In this paper, we give both necessary and sufficient conditions for circulants to be hyper-Hamiltonian.

Let (a1, a2, . . . , ak) be a sequence of k pairwise distinct positive integers. The undirected circulant graph Gn(a1, a2, . . . , ak) has vertices i±a1, i±a2, . . . , i±a^k (mod n) adjacent to each vertex i, where a^j < n+1 2 for 1 ≤ j ≤ k. Similarly, the circulant digraph Gn(a1, a2, . . . , ak) has vertices i + a1, i + a2, . . . , i + a^k (mod n) adjacent to each vertex i, where a^j < n for 1 ≤ j ≤ k. The sequence {aj} is called the jump sequence, and the a^j s are called the jumps [2]. Hence, a circulant digraph Gn(a1, a2, . . . , ak) contains an edge (i.e., two opposite arcs) if it contains aⁱ such that aⁱ = n − a^j for some a^j . In particular, a circulant digraph Gn(a1, a2, . . . , ak) is equivalent to an undirected circulant Hⁿ if for every aⁱ there exists a^j such that aⁱ = n − a^j . Consequently, a Hamilton cycle in Gn(a1, a2, . . . , ak) needs to adhere to the directions of arcs.

Figure 1. Example of a circulant digraph Gn(a1, a2) = G15(1, 4) ' G15(4, 1).

This paper is organized as follows. In the next Section 2, we cover prior published results that we will leverage in the proofs of our theorems in the following sections. In Section 3, we give necessary and sufficient conditions in Theorem 3.1 for an arbitrary undirected circulant to be hyper-Hamiltonian. Section 4 covers directed circulants. First, in Theorem 4.1 we give the necessary and sufficient conditions for a circulant digraph with 2 jumps to be hyper-Hamiltonian. In the second part of Section 4 we focus and give some sufficient conditions for hyper-Hamiltonicity in circulant

digraph with arbitrary number of jumps.

2. Preliminary Results

There are five results that will be useful in proving our main theorem in the next section for undirected circulants, and one result (i.e., Theorem 2.4) pertaining to circulant digraphs that we will leverage in the last section of this paper. First, the following result was proved by Lov´asz.

Theorem 2.1 ([7]). Every connected circulant is Hamiltonian.

Second, we examined pancyclic and edge-bipancyclic properties in undirected circulants [5]. G(V, E) is edge-bipancyclic if every edge e, e ∈ E(G), is included in a cycle of length 2k for every value of 2k, where |V (G)| ≥ 2k ≥ 4. Furthermore, G(V, E) is pancyclic if it contains cycles of length k for every value of k, where |V (G)| ≥ k ≥ 3. We obtained the following two results:

Theorem 2.2 ([5]). Let G be a connected circulant of order n with at least two jumps. Then, G is edge-bipancyclic.

Theorem 2.3 ([5]). Let G be a connected circulant of order n and girth 3. Then, G is pancyclic.

Both results are related to hyper-Hamiltonicity of undirected circulants, which will be exploited in the proof of our main theorem of Section 3.

We also need the following result due to Boesch and Tindell that pertains to undirected as well as directed circulants.

Theorem 2.4 ([2]). Circulant Gn(a1, a2, . . . , ak) is connected if and only if

\[\gcd(n, a_1, a_2, \dots, a_k) = 1.\]

Furthermore, we extended Theorem 2.4 as follows.

Theorem 2.5 ([3]). Circulant Gn(a1, a2, . . . , ak) consists of r connected components if and only if

\[\gcd(n, a_1, a_2, \dots, a_k) = r.\]

Since each connected component of any circulant is of identical size, having r from Theorem 2.5 establishes their size equal ⁿ r , which will be useful in the proofs in Sections 3-4.

3. Hyper-Hamiltonian Undirected Circulants

We now prove necessary and sufficient conditions for an arbitrary undirected and connected circulant to be hyper-Hamiltonian.

Theorem 3.1. A connected circulant Gn(a1, a2, . . . , ak) for k ≥ 2 is hyper-Hamiltonian if and only if either n is odd or at least one aⁱ is even.

Proof. Recall that \(G = G_n(a_1, a_2, \dots, a_k)\) has vertices \(v_0, v_1, \dots, v_{n-1}\). As G is vertex transitive and Hamiltonian by Theorem 2.1, it suffices to show that \(H = G - v_0\) has a Hamilton cycle.

We first assume that n is even and \(a_1, a_2, \ldots, a_k\) are odd, and we show that \(G = G_n(a_1, a_2, \ldots, a_k)\) is not hyper-Hamiltonian. Suppose G is hyper-Hamiltonian, so there exists a cycle C of length n-1. Without loss of generality assume we walk along W starting at \(v_0\). Since every jump \(a_i\) is odd then the following two conditions are satisfied in W: (1) if a current vertex v in W is even then the next vertex \(v = v \pm a_i \pmod{n}\) in W is odd, and (2) if a current vertex v is odd then the next vertex \(v = v \pm a_i \pmod{n}\) in W is even. Since \(v = v \pm a_i \pmod{n}\) in \(v = v \pm a_i \pmod{n}\) in \(v = v \pm a_i \pmod{n}\) in \(v = v \pm a_i \pmod{n}\) in \(v = v \pm a_i \pmod{n}\) which results in a simple cycle \(v = v \pm a_i \pmod{n}\) of odd length \(v = v \pm a_i \pmod{n}\) which proves our necessary condition of hypothesis.

For a sufficient condition of hyper-Hamiltonicity of G we consider the following two cases.

Case 1. n odd.

By Theorem 2.1 G contains a Hamilton cycle, and by Theorem 2.2 G is edge-bipancyclic. So, G also contains a Hamilton cycle in \(H = G - v_i\) for any vertex \(v_i\) in G. Hence, G is hyper-Hamiltonian in this case.

Case 2. n even and at least one of the jumps \(a_i\) is even.

Since n is even then according to Theorem 2.4 also at least one of the jumps \(a_j\) is odd. Without loss of generality assume \(a_1\) odd and \(a_k\) even. Let \(\gcd(n,a_1,a_2,\ldots,a_{k-1})=r_1\) and \(\gcd(n,a_k)=r_2\). Let \(v_i^j\) denote ith vertex in jth cycle formed by \(a_k\) in G. So, according to Theorem 2.5 \(v_1^j v_2^j \cdots v_{\frac{n}{r_2}}^j\) denotes jth cycle formed by \(a_k\) in G, where \(r_2 \geq j \geq 1\).

Let H be the subgraph of G consisting of all the edges \((i, i + a_k \pmod n)\). Since \(n, a_k\) are even, H must be the union of at least two pairwise disjoint cycles \(C_j\). Let G' be obtain from G by contracting each cycle \(C_j\) of H into a vertex. If j is the smallest number such that some cycle in H contains vertices 1 and \(1 + j \pmod n\), then the cycles of H containing vertices \(1, 2, \ldots, j\) are pairwise distinct and constitute all the cycles of H. Then the isomorphism \(i \to i+1 \pmod n\) of G induces an isomorphism of G', which proves that G' is a connected circulant. By Theorem 2.1, G' has a Hamilton cycle. This implies existence of a simple path \(P = v_1^1 v_1^2 \cdots v_1^{r_2} v_q^1\) in G. Consequently, according to Theorem 2.5 there are \(\gcd(n, a_1, a_2, \ldots, a_{k-1})\), which is odd, cycles \(C_i\) corresponding to a Hamilton cycle of G' formed by jumps \(a_1, \ldots, a_{k-1}\) in G as follows:

\[C_{1} = v_{1}^{1}v_{1}^{2} \cdots v_{1}^{r_{2}} v_{q_{1}}^{1}v_{q_{1}}^{2} \cdots v_{q_{1}}^{r_{2}} \cdots v_{z_{1}}^{1}v_{z_{1}}^{2} \cdots v_{z_{1}}^{r_{2}}v_{1}^{1},\] \[C_{2} = v_{2}^{1}v_{2}^{2} \cdots v_{2}^{r_{2}} v_{q_{2}}^{1}v_{q_{2}}^{2} \cdots v_{q_{2}}^{r_{2}} \cdots v_{z_{2}}^{1}v_{z_{2}}^{2} \cdots v_{z_{2}}^{r_{2}}v_{2}^{1},\] \[\cdots\]

\[C_{r_1} = v_{r_1}^1 v_{r_1}^2 \cdots v_{r_1}^{r_2} v_{q_{r_1}}^1 v_{q_{r_1}}^2 \cdots v_{q_{r_1}}^{r_2} \cdots v_{z_{r_1}}^1 v_{z_{r_1}}^2 \cdots v_{z_{r_1}}^{r_2} v_{r_1}^1,\]

where \(q_1 = q\). Hence,

\[q = b \cdot \gcd(n, a_1, a_2, \dots, a_{k-1}) \pmod{\frac{n}{\gcd(n, a_k)}} + 1\]

for some positive odd integer b. Furthermore, since \(r_1\) is odd then q is either 1 or can be assumed even. In particular, if \(\frac{n}{\gcd(n,a_k)}\) is odd and q greater than 1 then q is even based on a convenient orientation of cycles formed by \(a_k\) (i.e., if q is odd in one orientation then it is even in opposite orientation). On the other hand, if \(\frac{n}{\gcd(n,a_k)}\) is even then q has to be even as well.

orientation). On the other hand, if \(\frac{n}{\gcd(n,a_k)}\) is even then q has to be even as well. If \(\frac{n}{\gcd(n,a_k)}=3\) then \(a_k\) forms triangles in G and by Theorem 2.3 G is pancyclic. This in turn implies that G is hyper-Hamiltonian and we are done. Otherwise, without loss of generality consider a walk W in G from vertex \(v_1^1\).

Subcase 2.1. q = 1.

We start walk W with

\[W_2 = v_1^1 v_1^2 \cdots v_1^{r_2} v_2^{r_2},\]

which is followed by walks:

\[W_{3} = v_{2}^{1}v_{3}^{1} v_{3}^{2}v_{2}^{2} \cdots v_{3}^{r_{2}-2}v_{2}^{r_{2}-2} v_{2}^{r_{2}-1}v_{3}^{r_{2}-1} v_{3}^{r_{2}}v_{4}^{r_{2}},\] \[W_{4} = v_{4}^{1}v_{5}^{1} v_{5}^{2}v_{4}^{2} \cdots v_{5}^{r_{2}-2}v_{4}^{r_{2}-2} v_{4}^{r_{2}-1}v_{5}^{r_{2}-1} v_{5}^{r_{2}-1} v_{5}^{r_{2}}v_{4}^{r_{2}},\] \[\cdots\]

\[W_t = v_{2t-4}^1 v_{2t-3}^1 v_{2t-3}^2 v_{2t-4}^2 \cdots v_{2t-3}^{r_2-2} v_{2t-4}^{r_2-2} v_{2t-4}^{r_2-1} v_{2t-3}^{r_2-1} v_{2t-3}^{r_2} v_{2t-2}^{r_2},\]

where \(2t - 1 = \frac{n}{r_2}\), and followed by walk,

\[W_{t+1} = v_{2t-1}^{r_2} v_{2t-1}^1 v_1^1.\]

Hence, \(W = W_2W_3 \cdots W_tW_{t+1}\) is a closed walk representing a simple cycle of length n-1 in G that skips the vertex \(v_{2t-2}^1\). So, in this subcase G is hyper-Hamiltonian.

Subcase 2.2. q even.

If either q=2 or \(q=\frac{n}{\gcd(n,a_2)}\) then \(a_2\) forms a Hamilton cycle in G – a contradiction. So, we may assume \(\frac{n}{\gcd(n,a_2)}>q>2\). Let \(t_1=\frac{n}{r_1}\) be the size of a cycle induced by \(a_1\). We start walk W with

\[W_1 = v_1^1 v_1^2 \cdots v_1^{r_2} v_q^1,\]

followed by walks:

\[W_{2} = v_{q+1}^{1} v_{q+2}^{1} \cdots v_{t_{1}}^{1} v_{t_{1}}^{2} v_{t_{1}-1}^{2} \cdots v_{q+1}^{2} v_{q}^{2},\] \[W_{3} = v_{q+1}^{2} v_{q+2}^{2} \cdots v_{t_{1}}^{2} v_{t_{1}}^{3} v_{t_{1}-1}^{3} \cdots v_{q+1}^{3} v_{q}^{3},\] \[\cdots\]

\[W_{r_2} = v_{q+1}^{r_2-1} v_{q+2}^{r_2-1} \cdots v_{t_1}^{r_2-1} \ v_{t_1}^{r_2} v_{t_1-1}^{r_2} \cdots v_{q+1}^{r_2} v_q^{r_2},\]

and if \(r_2 \ge 4\) then subsequently followed by walks:

\[W_{r_2+1} = v_{q-1}^{r_2} v_{q-2}^{r_2} \cdots v_2^{r_2} v_2^{r_2-1} v_3^{r_2-1} \cdots v_{q-1}^{r_2-1},\] \[W_{r_2+2} = v_{q-1}^{r_2-2} v_{q-2}^{r_2-2} \cdots v_2^{r_2-2} v_2^{r_2-3} v_3^{r_2-3} \cdots v_{q-1}^{r_2-3},\]

· · ·

\[W_{r_2+\frac{r_2-2}{2}}=v_{q-1}^4v_{q-2}^4\cdots v_2^4\ v_2^3v_3^3\cdots v_{q-1}^3.\]

If q − 1 > 3 then W1W² · · · W^r2⁺ r2−2 is followed by walk:

\[W_{r_2 + \frac{r_2 - 2}{2} + 1} = v_{q-1}^2 v_{q-1}^1 v_{q-2}^1 v_{q-2}^2 v_{q-3}^2 v_{q-3}^1 v_{q-4}^1 v_{q-4}^2 \cdots v_5^2 v_5^1 v_4^1 v_4^2.\]

Otherwise, W^r2⁺ r2−2 ² +1 is skiped. We end walk ^W1W² · · · ^Wr2⁺ r2−2 2 (W^r2⁺ r2−2 ² +1) with

\[W_{r_2+\frac{r_2-2}{2}+2}=v_3^2v_3^1v_2^1v_1^1.\]

So, in this subcase W is a closed walk representing a simple cycle of length n − 1 in G that skips the vertex v 2 2 . Hence, in this case G is hyper-Hamiltonian. Consequently, Cases 1-2 prove a sufficient condition for hyper-Hamiltonicity of G.

4. Hyper-Hamiltonian Circulant Digraphs

In this section, we first prove the necessary and sufficient conditions for a connected circulant digraphs with two jumps to be hyper-Hamiltonian. For convenience and better clarity in this section let vi±^j denote vertex i ± j taken modulo n.

Theorem 4.1. A connected circulant digraph Gn(a1, a2) is hyper-Hamiltonian if and only if either a¹ ≡ 2a² (mod n) or a² ≡ 2a¹ (mod n).

Proof. Without loss of generality, we first assume a² ≡ 2a¹ (mod n) for a sufficient condition. If gcd(n, a1) > 1 then gcd(n, a1, a2) > 1 and by Theorem 2.4 G is disconnected. So, assume gcd(n, a1) = 1. Then the isomorphism i → i + a¹ (mod n) of G induces circulant digraph G0 n (1, 2) ' Gn(a1, a2). Let CG⁰, CG0−v¹ denote the Hamilton cycles in G⁰ and G⁰−v1, respectively. Consequently, CG⁰ = v0v1v² · · · vn−1v⁰ and CG0−v¹ = v0v² · · · vn−1v0, which proves our sufficient condition.

For a necessary condition, assume a¹ 6= 2a² (mod n), a² 6= 2a¹ (mod n), and G is hyper-Hamiltonian. Without loss of generality assume H = G − v^a1 to have a Hamilton cycle CH. Such a cycle C^H must be induced by both jumps. Then, H contains either path Q¹ = v0v^a2 v^a2+a¹ v^a2+2a¹ or path Q² = v^a1−a² v2a1−a² v2a¹ v2a1+a² .

Case 1. H contains Q1.

If C^H is of the form v0v^a2 v^a2+a¹ v^a2+2a¹ · · · v^a2+z1a¹ where a² + z1a¹ ≡ 0 (mod n) then z¹ = n−2, which implies a² ≡ 2a¹ (mod n) – a contradiction. Otherwise, let z¹ be the largest positive integer for which C^H contains path P⁰ = v0v^a2 v^a2+a¹ v^a2+2a¹ · · · v^a2+z1a¹ . Then P⁰ implies

\[P_1 = v_{a_2-a_1}v_{(a_2-a_1)+a_2}v_{(a_2-a_1)+a_2+a_1}v_{(a_2-a_1)+a_2+2a_1}\cdots v_{(a_2-a_1)+a_2+a_1a_1}\]

in CH, since otherwise the vertices v^a1 , v^a2−a¹ would not be visited in CH. No successive path Pⁱ in C^H can start with v^a1 because it would imply all (i.e., at least 3) vertices in Pⁱ to be unvisited. Hence, by induction every path Pⁱ in C^H must be of the following form

\[P_i = v_{i(a_2-a_1)}v_{i(a_2-a_1)+a_2}v_{i(a_2-a_1)+a_2+a_1}v_{i(a_2-a_1)+a_2+2a_1}\cdots v_{i(a_2-a_1)+a_2+z_1a_1},\]

consisting of exactly \(z_1\) arcs of the form \((j, j + a_1 \pmod n)\). On the other hand, the unvisited vertex \(v_{a_1}\) and \(P_0\) imply a path \(P_x = v_{2a_1}v_{2a_1+a_1}v_{2a_1+2a_1}\cdots v_{2a_1+(z_1-1)a_1}\), with \(z_1-1\) arcs of the form \((j, j + a_1 \pmod n)\) in \(C_H\) – a contradiction.

Case 2. H contains \(Q_2\).

If \(C_H\) is of the form \(v_{a_1-a_2}v_{2a_1-a_2}v_{2a_1}v_{2a_1+a_2}\cdots v_{2a_1+z_2a_2}\) where \(2a_1+z_2a_2\equiv a_1-a_2\pmod n\) then \(z_2=n-2\), which implies \(2(a_1-a_2)\equiv a_1-a_2\pmod n\) – a contradiction. Otherwise, let \(z_2\) be the largest positive integer for which \(C_H\) contains path \(P_0=v_{a_1-a_2}v_{2a_1-a_2}v_{2a_1}v_{2a_1+a_2}\cdots v_{2a_1+z_2a_2}\). Then \(P_0\) implies

\[P_1 = v_{(a_1 - a_2) + a_1 - a_2} v_{(a_1 - a_2) + 2a_1 - a_2} v_{(a_1 - a_2) + 2a_1} v_{(a_1 - a_2) + 2a_1 + a_2} \cdots v_{(a_1 - a_2) + 2a_1 + z_2 a_2}\]

in \(C_H\), since otherwise the vertices \(v_{a_1}, v_{2(a_1-a_2)}\) would not be visited in \(C_H\). No successive path \(P_i\) in \(C_H\) can start with \(v_{a_1}\) because it would imply all vertices in \(P_i\) to be unvisited. Consequently by induction every \(P_i\) in \(C_H\) has to be of the following form

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

consisting of exactly \(z_2+1\) arcs of the form \((j,j+a_2 \pmod n)\). On the other hand, the unvisited \(v_{a_1}\) and \(P_0\) imply a path \(P_y=v_{a_1+a_2}v_{a_1+2a_2}v_{a_1+3a_2}\cdots v_{a_1+(z_2+1)a_2}\), with \(z_2\) arcs of the form \((j,j+a_2 \pmod n)\) in \(C_H\) – a contradiction.

Consequently, the contradictions of Cases 1-2 prove a necessary condition. \(\Box\)

For the general case of a circulant digraph \(G = G_n(a_1, a_2, \dots, a_k)\) the problem of deciding whether or not G is hyper-Hamiltonian is more challenging since it is an open problem in respect to which circulant digraphs are Hamiltonian in general. Hence, in the rest of this section we focus on some sufficient conditions for hyper-Hamiltonicity of G.

For given integers \(s_1, s_2, \ldots, s_k\) define \(P_i\) as follows:

P_{i} = v_{i+a_{1}}v_{i+2a_{1}} \cdots v_{i+s_{1}a_{1}}
v_{i+s_{1}a_{1}+a_{2}}v_{i+s_{1}a_{1}+2a_{2}} \cdots v_{i+s_{1}a_{1}+s_{2}a_{2}}
\cdots
v_{i+s_{1}a_{1}+s_{2}a_{2}+\cdots+s_{k-1}a_{k-1}+a_{k}}v_{i+s_{1}a_{1}+s_{2}a_{2}+\cdots+s_{k-1}a_{k-1}+2a_{k}} \cdots v_{i+s_{1}a_{1}+s_{2}a_{2}+\cdots+s_{k-1}a_{k-1}+s_{k}a_{k}}.

Let \(C_G(s_1, s_2, \ldots, s_k)\) denote a Hamilton cycle in G of the form \(P_0P_cP_{2c}\cdots P_m\pmod n\) for some positive integers c, m, where \(m+s_1a_1+s_2a_2+\cdots+s_ka_k\equiv 0\pmod n\). The following theorem from [4] will be useful in obtaining some sufficient conditions for hyper-Hamiltonicity in circulant digraphs.

Theorem 4.2 ([4]). Let \(G_{rs}(a_1, a_2, \ldots, a_k)\) be a connected circulant digraph. Let \(s_i\) be integers such that \(\frac{rs}{a_i} > s_i \ge 1\) and \(s = s_1 + s_2 + \cdots + s_k\). Let t be a positive integer and \(ts = \frac{rs}{\gcd(rs, a_j)}\) for some \(a_j\). If \(\gcd(rs, s_1a_1 + s_2a_2 + \cdots + s_ka_k) = s\) and \(a_i \equiv a_j \pmod{s}\) then \(G_{rs}(a_1, a_2, \ldots, a_k)\) has a Hamilton cycle \(C_G(s_1, s_2, \ldots, s_k)\).

Since a Hamilton cycle is explicitly identified in Theorem 4.2, we can leverage that in determining sufficient conditions for hyper-Hamiltonicity in circulant digraphs as follows.

Theorem 4.3. Let \(G_{rs}(a_1, a_2, ..., a_k)\) be a connected circulant digraph. Let \(s_i\) be integers such that \(\frac{rs}{a_i} > s_i \ge 1\) and \(s = s_1 + s_2 + \cdots + s_k\). Let t be a positive integer such that \(ts = \frac{rs}{\gcd(rs, aj)}\) for some \(a_j\). \(G_{rs}(a_1, a_2, ..., a_k)\) is hyper-Hamiltonian if the following conditions are satisfied:

• (1) \(\gcd(rs, s_1a_1 + s_2a_2 + \dots + s_ka_k) = s\),
• (2) \(a_i \equiv a_i \pmod{s}\),
• (3) \(a_i + a_j \equiv a_t \pmod{rs}\) for at least one combination of \(i, j, t, or a_i \equiv 2a_q \pmod{rs}\) and \(s_q \geq 2\) for some i, q.

Proof. If (1) and (2) are satisfied then by Theorem 4.2 \(G = G_{rs}(a_1, a_2, \ldots, a_k)\) has a Hamilton cycle of form \(C_G(s_1, s_2, \ldots, s_k)\). Hence, it suffices to show that G - v also has a Hamilton cycle for some arbitrary \(v \in V(G)\) since G is vertex transitive. If \(s_q \geq 2\) for some \(q, k \geq q \geq 1\), then by definition corresponding \(C_G = C_G(s_1, s_2, \ldots, s_k)\) contains two consecutive arcs \(a_q\), i.e., \(C_G = \cdots a_q a_q \cdots\). So, if there exists \(a_i\) in G such that \(a_i \equiv 2a_q \pmod{rs}\) then \(a_q a_q\) in \(C_G\) can be substituted with \(a_i\) resulting in a Hamilton cycle in G - v. Otherwise, assume \(a_i + a_j \equiv a_t \pmod{rs}\) for some combination of i, j, t. Let \((a'_1, a'_2, \ldots, a'_k)\) be any permutation of \((a_1, a_2, \ldots, a_k)\). If (1) and (2) are satisfied then \(\gcd(rs, s'_1 a'_1 + s'_2 a'_2 + \cdots + s'_k a'_k) = s\) and \(a'_i \equiv a'_j \pmod{s}\) are satisfied for some permutation \((s'_1, s'_2, \ldots, s'_k)\) of \((s_1, s_2, \ldots, s_k)\) too. Furthermore, according to Theorem 4.2 \(C_G(s_1, s_2, \ldots, s_k)\) exists, which implies that \(C_{G'}(s'_1, s'_2, \ldots, s'_k)\) also exists in \(G' = G_{rs}(a'_1, a'_2, \ldots, a'_k)\). Hence, for \(a_i + a_j \equiv a_t \pmod{rs}\) we conveniently choose \((a'_1, a'_2, \ldots, a'_k)\), so \(a'_1 = a_i, a'_2 = a_j\), and \(a'_k = a_t\). Consequently, \(C_{G'}(s'_1, s'_2, \ldots, s'_k)\) induces a Hamilton cycle in G' - v by substituting one occurrence of two arcs \(a'_1 a'_2\) with a single arc \(a'_k\), which completes this proof.

Finally, the sufficient condition for the hyper-Hamiltonicity of an arbitrary circulant digraph can be extended from circulant digraph with 2 jumps based on Theorem 4.1, as follows.

Theorem 4.4. A connected circulant digraph \(G_n(a_1, a_2, ..., a_k)\) is hyper-Hamiltonian if it contains two jumps \(a_i, a_j\) such that \(a_i \equiv 2a_j \pmod{n}\) and \(\gcd(n, a_j) = 1\).

Proof. If \(G = G_n(a_1, a_2, \ldots, a_k)\) contains \(a_j\) such that \(\gcd(n, a_j) = 1\) then according to Theorem 2.4 our G contains a spanning connected circulant digraph \(G'_n(a_i, a_j)\) for any \(a_i\) in G. Furthermore, if \(a_i \equiv 2a_j \pmod{n}\) then \(a_i \neq a_j\) and by Theorem 4.1 G is hyper-Hamiltonian.

In closing, we note that \(a_i \equiv 2a_j \pmod{n}\) imply hyper-Hamiltonicity of \(G_n(a_1, a_2, \dots, a_k)\) in Theorems 4.3-4.4 under different additional conditions. In particular, Theorem 4.4 also requires \(\gcd(n, a_i) = 1\) while Theorem 4.3 does not require \(\gcd(n, a_i) = 1\), but other conditions.

Acknowledgement

I would like to extend my gratitude to the anonymous referee for valuable comments and suggestions, which resulted in improved presentation of this paper.

References

• [1] T. Araki, Hyper hamiltonian laceability of Cayley graphs generated by transpositions, Networks, 48 (2006), 121–124.
• [2] F.T. Boesch and R. Tindell, Circulants and their connectivity, J. Graph Theory, 8 (1984), 129–138.
• [3] Z.R. Bogdanowicz, Isomorphism between circulants and Cartesian products of cycles, Discrete Applied Math., 226 (2017), 40–43.
• [4] Z.R. Bogdanowicz, Hamilton cycles in circulant digraphs with prescribed number of distinct jumps, Discrete Math., 309 (2009), 2100–2107.
• [5] Z.R. Bogdanowicz, Pancyclicity of connected circulant graphs, J. Graph Theory, 22 (1996), 167–174.
• [6] R.R. Del-Vecchio, C.T.M. Vinagre, and G.B. Pereira, Hyper-Hamiltonicity in graphs: some sufficient conditions, Elec. Notes Disc. Math., 62 (2017), 165–170.
• [7] L. Lov´asz, Combinatorial problems and exercises, North-Holland, Amsterdam, 1979.
• [8] T. Mai, J. Wang, and L. Hsu, Hyper-Hamiltonian generalized Petersen graphs, Comput. and Math. with Appl., 55 (2008), 2076–2085.
• [9] A. Shabbir, Fault-tolerant designs in lattice networks on the Klein bottle, Electron. J. Graph Theory Appl., 2 (2) (2014), 99–109.