On the number of Hamiltonian cycles in the generalized Petersen graph

1. Introduction

Let \(n, k\) be positive integers. The generalized Petersen graph \(G(n, k)\) is a cubic graph with vertex set \[V(G(n, k)) = \{v_i\}_{0 \leq i < n} \cup \{w_i\}_{0 \leq i < n},\] and edge set \[E(G(n, k)) = \{v_i v_{i+1}\}_{0 \leq i < n} \cup \{w_i w_{i+k}\}_{0 \leq i < n} \cup \{v_i w_i\}_{0 \leq i < n},\] where the indices are taken modulo \(n\). A Hamiltonian cycle of a graph is a cycle of edges that visits each vertex exactly once. Schwenk [1] found the number of Hamiltonian cycles in \(G(n, k)\) for \(k=2\), and asked for a corresponding enumeration for higher values of \(k\). The objective of this paper is to give initial conditions and linear recurrence relations in the cases \(k=3\) and \(k=4\), from which explicit formulae can be constructed based on the roots of the characteristic polynomials.

To this end, we introduce the graph \(G'(n, k)\) with the same vertex set and edge set as \(G(n, k)\), except for the additional vertices \(L_0, \dotsc, L_k\), \(R_0, \dotsc, R_k\), and the edges \(v_0 v_{n-1}\), \(w_0 w_{n-k}, \dotsc, w_{k-1} w_{n-1}\) replaced by \(v_0 L_0\), \(w_0 L_1, \dotsc,\) \(w_{k-1} L_k\), \(v_{n-1} R_0\), \(w_{n-k} R_1, \dotsc, w_{n-1} R_k\). Figure 1 shows this graph in the case \(k=3\).

The visible edges in the figure are called the outer edges. Generally, those that are incident with at least one of \(v_0, v_1, \dotsc, v_{k-1}\), \(w_0, w_1, \dotsc, w_{k-1}\) are called the outer edges on the left hand side, and those that are incident with at least one of \(v_{n-k}, v_{n-k+1}, \dotsc, v_{n-1}\), \(w_{n-k}, w_{n-k+1}, \dotsc, w_{n-1}\) are called the outer edges on the right hand side.

Consider a subgraph \(\Gamma\) of \(G'(n, k)\) with the same vertex set as that of \(G'(n, k)\) for which each vertex of degree 3 in \(G'(n, k)\) has degree 2 in \(\Gamma\), and containing no cycles except possibly one that constitutes the whole of \(\Gamma\). Such subgraphs are called admissible subgraphs of \(G'(n, k)\). Each admissible subgraph \(\Gamma\) is associated with a list of pairs of the vertices among \(L_0, \dotsc, L_k\), \(R_0\), \(R_1, \dotsc, R_k\) of degree 1 in \(\Gamma\) (called loose ends henceforth) that are in the same connected component. This list is called a list of connections.

For any given \(k\), there is a finite number of possible intersections of an admissible subgraph and the outer edges on either side, which we label \(S_1, S_2, \dotsc\). For \(k=3\), there are 33 possibilities, as seen in Table 1. For \(k=4\) and \(k=5\), the number of possibilities is 85 and 217, respectively.

Suppose \(\Gamma\) is an admissible subgraph of \(G'(n, k)\). If the intersection of \(\Gamma\) and the outer edges on the left hand side is \(S_{n_L}\), the intersection of \(\Gamma\) and the outer edges on the right hand side is \(S_{n_R}\) and the list of connections is \(\lambda\), we say that the \(signature\) of \(\Gamma\) is \((n_L, n_R, \lambda)\). For \(k=3\), there are 1705 distinct signatures in which all the loose ends are accounted for in the list of connections, and two loose ends are in the same pair if they are connected through the outer edges on one side. For example, if \(n_L=8\), then necessarily \((L_1, L_2) \in \lambda\). Not all of them can be realized; for example, no admissible subgraph can have signature \((1, 7, \{(R_0, R_3)\})\). For \(k = 4\) and \(k = 5\), the number of signatures is 25675 and 455835, respectively.

For a fixed \(k\), let \[\label{sequence} u^{(n_L, n_R, \lambda)}_n, \tag{1}\] denote the number of admissible subgraphs of \(G'(n, k)\) with signature \((n_L, n_R, \lambda)\). We are going to find a linear recurrence relation satisfied by all these sequences for \(k=3\) and for \(k=4\).

Let \(H_k\) denote the set of signatures that pass the following test.

Thus, the number of Hamiltonian cycles in \(G(n, k)\) is given by \[\label{hamiltonian} h_k(n) = \sum_{(n_L, n_R, \lambda) \in H_k} u^{(n_L, n_R, \lambda)}_n. \tag{2}\]

As a sum of (1) over a subset of the possible signatures, \(h_k(n)\) also satisfies any linear recurrence relation satisfied by all the individual sequences.

2. The graph \(\sigma_k\) of signatures

The directed graph \(\sigma_k\) is defined as follows. \(V(\sigma_k)\) is the set of all signatures. Thus, the terms “vertices” and “signatures” in \(\sigma_k\) can be used interchangeably, but we will primarily use the latter. Given a signature \((n_L, n_R, \lambda)\), let \(\Gamma\) be a hypothetical (not necessarily realizable) admissible subgraph of \(G'(n, k)\) having that signature, for some \(n\). The graph \(G'(n-1, k)\) can be obtained by removing \(v_{n-1} R_0\), \(v_{n-1} w_{n-1}\) and \(w_{n-1} R_k\) from \(E(G'(n, k))\) and \(R_0\) and \(R_k\) from \(V(G'(n, k))\), and renaming \(v_{n-1}\) to \(R_0\), \(R_{k-1}\) to \(R_k\), \(R_{k-2}\) to \(R_{k-1}, \dotsc, R_1\) to \(R_2\) and \(w_{n-1}\) to \(R_1\). If \((n_L, n'_R, \lambda')\) is a possible signature of the intersection of \(\Gamma\) and \(G'(n – 1, k)\) thus constructed, then the arc \(((n_L, n'_R, \lambda'), (n_L, n_R, \lambda))\) is in \(E(\sigma_k)\).

For the remainder of this Section, we outline the possible signatures of the intersection of \(\Gamma\) and \(G'(n-1, k)\).

\(v_{n-k-1}w_{n-k-1}\) can not be in \(E(\Gamma)\) if either \(v_{n-k-1}v_{n-k}, \dotsc, v_{n-2}v_{n-1}\), \(v_{n-1}w_{n-1}\) and \(w_{n-k-1}w_{n-1}\) are all in \(E(\Gamma)\), as a cycle not constituting the whole of \(\Gamma\) would be formed, or if \(v_{n-k-1}\) and \(w_{n-k-1}\) are connected through the outer edges on the right hand side to two loose ends \(x\) and \(y\) such that \((x, y) \not \in \lambda\).

There are five possibilities for which of the edges \(v_{n-1} R_0\), \(v_{n-1} w_{n-1}\), \(w_{n-1} R_k\) are in \(E(\Gamma)\): All three, any two (which covers three possibilities), or only \(v_{n-1} w_{n-1}\). Here is how to construct \(\lambda'\) from the list of connections \(\lambda\) in \(\Gamma\) in each case, before the renaming step (recall that \(v_{n-1}\) is to be renamed to \(R_0\), \(R_{k-1}\) to \(R_k\) etc.).

• If all three edges are in \(E(\Gamma)\) and \(\lambda\) contains other pairs than \((R_0, R_k)\), then remove \((R_0, R_k)\). Note that if \(\lambda\) does not contain other pairs than \((R_0, R_k)\), then the edges other than those three form a cycle.

• If only \(v_{n-1} R_0\) and \(v_{n-1} w_{n-1}\) are in \(E(\Gamma)\), replace \(R_0\) by \(w_{n-1}\).

• If only \(v_{n-1} w_{n-1}\) and \(w_{n-1} R_k\) are in \(E(\Gamma)\), replace \(R_k\) by \(v_{n-1}\).

• If only \(v_{n-1} R_0\) and \(w_{n-1} R_k\) are in \(E(\Gamma)\), replace \(R_0\) by \(v_{n-1}\) and \(R_k\) by \(w_{n-1}\).

• Suppose only \(v_{n-1} w_{n-1}\) is in \(E(\Gamma)\). If \(\lambda\) is empty, then add \((v_{n-1}, w_{n-1})\). Otherwise, some \((x, y) \in \lambda\) is to be replaced by \((x, v_{n-1})\), \((y, w_{n-1})\). Any loose end that is connected to \(v_{n-1}\) through the edges on the right hand side other than \(v_{n-1} w_{n-1}\) must take the role of \(x\), and any loose end that is connected to \(w_{n-1}\) through the edges on the right hand side other than \(v_{n-1} w_{n-1}\) must take the role of \(y\). If one of \(x\) and \(y\) is determined in this way, the other one is determined by \(\lambda\). If neither of them is determined in this way, any \((x, y) \in \lambda\) for which \(x\) and \(y\) are not connected through the outer edges on one side will do.

3. Linear recurrence relations and characteristic polynomials

If \(k=3\), then simply by inspecting Table 1, we find that the initial value of (1) for \(n=k\) is 1 when \((n_L, n_R, \lambda)\) is one of \((1, 1, \{(R_0, R_3), (R_1, R_2)\})\), \((2, 2, \{(L_3, R_0), (R_1, R_2)\})\), \((3, 3, \{(L_2, R_1), (R_0, R_3)\})\) and so on, and 0 in all other cases. Similarly, the initial values follow directly from the corresponding set \(\{S_i\}\) for other values of \(k\). For \(n > k\), we have \[\label{sigma_relation} u^{(n_L, n_R, \lambda)}_n = \sum_{((n_L, n'_R, \lambda'), (n_L, n_R, \lambda)) \in E(\sigma_k)} u^{(n_L, n_R', \lambda')}_{n-1}, \tag{3}\] from which we we would like to obtain a linear recurrence relation \[u^{(n_L, n_R, \lambda)}_n + p_{d-1} u^{(n_L, n_R, \lambda)}_{n-1} + \dotsc + p_0 u^{(n_L, n_R, \lambda)}_{n-d}=0,\] that holds for all \(n \geq n_0\) for some \(n_0\). Such a recurrence relation is associated with a characteristic polynomial \[p(x) = p_dx^d + p_{d-1}x^{d-1}d + \dotsc + p_1x + p_0,\] with \(p_d=1\). We say that \(p(x)\) is a characteristic polynomial for \(\{u_n\}\) for \(n \geq n_0\) if \[p_d u_n + p_{d-1} u_{n-1} + \dotsc + p_0 u_{n-d}=0,\] holds for all \(n \geq n_0\).

Generally, for any directed graph \(D\), we can define sequences \(\{u^v_n\}_{v \in E(D)}\) by a set of initial conditions and the relation \[\label{general_relation} u^v_n = \sum_{(v', v) \in E(D)} u^{v'}_{n-1}, \tag{4}\] corresponding to (3).

The monic polynomial of smallest degree that is a characteristic polynomial for all these sequences for a particular set \(I\) of initial conditions and sufficiently large \(n\) is called the minimal characteristic polynomial on \((D, I)\). A polynomial that is a characteristic polynomial for all these sequences for any set of initial conditions and sufficiently large \(n\) is called a universal characteristic polynomial on \(D\), and the monic one with the smallest degree is called the minimal universal characteristic polynomial on \(D\). By Corollary 3.2, the minimal characteristic polynomial on \((D, I)\) divides the minimal universal characteristic polynomial on \(D\) regardless of \(I\). Let \(I_k\) denote the set of initial conditions for the sequences (1).

In order to prove that a linear recurrence relation is valid for all of the sequences for all sufficiently large \(n\), it suffices to verify that it holds for all the sequences for one value of \(n\).

A directed graph \(D\) can be partitioned into strongly connected components (SCCs), i.e., maximal subgraphs in which any vertex can reach any other. An SCC \(\xi \subseteq D\) for which there is no arc from a vertex in \(D \backslash \xi\) to a vertex in \(\xi\) is called a source SCC, and one for which there is no arc from a vertex in \(\xi\) to a vertex in \(D \backslash \xi\) is called a sink SCC.

Suppose that for each SCC \(\xi \subseteq D\), the minimal universal characteristic polynomial on \(\xi\) is known, called \(p^{(\xi)}(x)\) of degree \(d_{\xi}\). Then Algorithm 1 produces a characteristic polynomial on \((D, I)\). In view of Lemma 3.1, the step in the bottom of the flowchart does not invalidate the universal characteristic polynomials on the remaining SCCs.

Analysis of \(\sigma_k\) has shown that for \(k=3\), each SCC is isomorphic to one out of 7 directed graphs with at most 24 vertices, and for \(k=4\), each SCC is isomorphic to one out of 11 directed graphs with at most 122 vertices. These are small enough that we can find universal characteristic polynomials using iterated changes of variables. In order to find the minimal one for an SCC \(\xi\subseteq D\), we can run the iterated changes of variables procedure several times and take the greatest common divisor, and/or we can check if some divisor of any given universal characteristic polynomial is also a characteristic polynomial if we set \[u^{(v)}_k= \begin{cases} 1 &\quad\text{if }v = v_0\\ 0 &\quad\text{otherwise,} \end{cases}\] regardless of \(v_0 \in V(\xi)\). We set the initial values for \(n=k\), as (1) is only defined for \(n \geq k\).

Algorithm 1

For one vertex \(v\) from each sink SCC of \(D\), set \(P^{(v)}(x) = 1\), let \(\rho(v) \subseteq D\) be induced by all vertices that can reach \(v\), define the sequences \(\{u^{(w)}_n\}_{w \in \rho(v)}\) by \(I\) and (4), and execute this flowchart. Return the least common multiple of the polynomials it produces.

4. Examples

As an example of the analysis for a single SCC, consider \(\xi \subset \sigma_3\) consisting of \[\begin{aligned} &\{ (4, 32, \{(L_2, R_2), (L_3, R_1)\}), (4, 30, \{(L_2, R_1), (L_3, R_0)\}), \\ & (4, 26, \{(L_2, R_3), (L_3, R_0)\}), (4, 11, \{(L_2, R_2), (L_3, R_3)\}), \\ & (4, 27, \{(L_2, R_1), (L_3, R_2), (R_0, R_3)\}), (4, 16, \{(L_2, R_2), (L_3, R_1)\}), \\ & (4, 4, \{(L_2, R_1), (L_3, R_0)\}), (4, 23, \{(L_2, R_3), (L_3, R_1), (R_0, R_2)\}), \\ & (4, 10, \{(L_2, R_2), (L_3, R_1)\}), (4, 13, \{(L_2, R_2), (L_3, R_3), (R_0, R_1)\}), \\ & (4, 33, \{(L_2, R_1), (L_3, R_2), (R_0, R_3)\}), (4, 33, \{(L_2, R_3), (L_3, R_1), (R_0, R_2)\}), \\ & (4, 33, \{(L_2, R_2), (L_3, R_3), (R_0, R_1)\})\}, \end{aligned}\] and the corresponding sequences \(\{u^{(1)}_n\}\) through \(\{u^{(13)}_n\}\). The relations for these sequences, based on (3), are as follows for \(n \geq 4\).

Using only \(\{u_n^{(1)}\}\), \(\{u_n^{(2)}\}\), \(\{u_n^{(3)}\}\) and \(\{u_n^{(11)}\}\) (those with more than one term in their relation), we have \(u_n^{(4)} = u_{n-1}^{(3)}\), \(u_n^{(5)} = u_{n-2}^{(3)}\), \(u_n^{(6)} = u_{n-3}^{(3)}\), \(u_n^{(7)} = u_{n-4}^{(3)}\), \(u_n^{(8)} = u_{n-3}^{(3)}\), \(u_n^{(9)} = u_{n-4}^{(3)}\), \(u_n^{(10)} = u_{n-4}^{(3)}\), \(u_n^{(12)} = u_{n-1}^{(11)}\), \(u_n^{(13)} = u_{n-2}^{(11)}\), and the relations \[ u_n^{(1)} = u_{n-1}^{(11)} + u_{n-2}^{(11)},\label{eq6}\ \tag{6}\] \[u_n^{(2)} = u_{n-1}^{(1)} + u_{n-5}^{(3)},\label{eq7}\ \tag{7}\] \[u_n^{(3)} = u_{n-1}^{(2)} + u_{n-5}^{(3)},\label{eq8}\ \tag{8}\] \[u_n^{(11)} = u_{n-5}^{(3)} + u_{n-3}^{(11)}.\label{eq9} \tag{9}\]

(6) and (9 gives \[\begin{aligned} \label{eq10} u_n^{(1)} & = u_{n-6}^{(3)} + u_{n-4}^{(11)} + u_{n-7}^{(3)} + u_{n-5}^{(11)} \nonumber \\ & = u_{n-3}^{(1)} + u_{n-6}^{(3)} + u_{n-7}^{(3)}. \end{aligned} \tag{10}\]

(8) and (10) gives \[\begin{aligned} \label{eq11} u_n^{(1)} & = u_{n-3}^{(1)} + u_{n-7}^{(2)} + u_{n-11}^{(3)} + u_{n-8}^{(2)} + u_{n-12}^{(3)} \nonumber \\ & = u_{n-3}^{(1)} + u_{n-7}^{(2)} + u_{n-8}^{(2)} + u_{n-5}^{(1)} – u_{n-8}^{(1)} \nonumber \\ & = u_{n-3}^{(1)} + u_{n-5}^{(1)} – u_{n-8}^{(1)} + u_{n-7}^{(2)} + u_{n-8}^{(2)}, \end{aligned} \tag{11}\] and (7) and (8) gives \[\begin{aligned} \label{eq12} u_n^{(2)} & = u_{n-1}^{(1)} + u_{n-6}^{(2)} + u_{n-10}^{(3)} \nonumber \\ & = u_{n-1}^{(1)} + u_{n-6}^{(2)} + u_{n-5}^{(2)} – u_{n-6}^{(1)} \nonumber \\ & = u_{n-1}^{(1)} – u_{n-6}^{(1)} + u_{n-5}^{(2)} + u_{n-6}^{(2)}. \end{aligned} \tag{12}\]

Finally, (11) and (12) gives \[\begin{aligned} u_n^{(1)} = & u_{n-3}^{(1)} + u_{n-5}^{(1)} – u_{n-8}^{(1)} + u_{n-8}^{(1)} – u_{n-13}^{(1)} + u_{n-12}^{(2)} \\ & + u_{n-13}^{(2)} + u_{n-9}^{(2)} – u_{n-14}^{(1)} + u_{n-13}^{(1)} + u_{n-14}^{(2)}\\ = & u_{n-3}^{(1)} + u_{n-5}^{(1)} + u_{n-9}^{(1)} – u_{n-13}^{(1)} – u_{n-1}^{14} + u_{n-5}^{(1)} – u_{n-8}^{(1)} \\ & -u_{n-10}^{(1)} + u_{n-13}^{(1)} + u_{n-6}^{(1)} – u_{n-9}^{(1)} – u_{n-11}^{(1)} + u_{n-14}^{(1)} \\ = & u_{n-3}^{(1)} + 2u_{n-5}^{(1)} + u_{n-6}^{(1)} – u_{n-8}^{(1)} – u_{n-10}^{(1)} – u_{n-11}^{(1)}, \end{aligned}\] which gives us a universal characteristic polynomial \(x^{11}-x^8-2x^6-x^5+x^3+x+1\). However, it factorizes as \[x^{11}-x^8-2x^6-x^5+x^3+x+1 = (x-1)(x^4+x^3+x^2+x+1)(x^6-x^3-x-1),\] and we can check whether some proper divisor is also a universal characteristic polynomial. Specifically, we can let \(j \in \{1, \dotsc, 13\}\) and set \(u^{(j)}_3=1\) and \(u^{(i)}_3=0\) for \(i \neq j\). It turns out that \(u^{(i)}_{13} – u^{(i)}_{10}-u^{(i)}_8-u^{(i)}_7=0\) for all \(i \in \{1, \dotsc, 13\}\) regardless of \(j\). By Lemma 3.3, we then have \(u^{(i)}_{n} – u^{(i)}_{n-3}-u^{(i)}_{n-5}-u^{(i)}_{n-6}=0\) for all \(n \geq 13\) for all \(i\), and since any set of initial values is a linear combination of the ones we have tried out, \(x^6-x^3-x-1\) is a universal characteristic polynomial on \((\xi, I_3)\). Since it is irreducible and \(\xi\) is nontrivial, it must be minimal.

As an example of an execution of the flowchart in Algorithm 1, let \[v=(4, 16, \{(L_2, L_3), (R_1, R_2)\}).\]

The subgraph \(\rho(v) \subset \sigma_3\) consists of the SCCs

\[\begin{aligned} \xi_1 = \{ & (4, 33, \{(L_2, R_0), (L_3, R_2), (R_1, R_3)\}), (4, 33, \{(L_2, R_0), (L_3, R_1), (R_2, R_3)\}), \\ & (4, 33, \{(L_2, R_0), (L_3, R_3), (R_1, R_2)\})\} \\ \xi_2 = \{ & (4, 33, \{(L_2, R_1), (L_3, R_0), (R_2, R_3)\}), (4, 33, \{(L_2, R_3), (L_3, R_0), (R_1, R_2)\}), \\ & (4, 33, \{(L_2, R_2), (L_3, R_0), (R_1, R_3)\})\} \\ \xi_3 = \{ & (4, 4, \{(L_2, R_0), (L_3, R_1)\}), (4, 26, \{(L_2, R_0), (L_3, R_3)\}), \\ & (4, 11, \{(L_2, R_3), (L_3, R_2)\}), (4, 27, \{(L_2, R_2), (L_3, R_1), (R_0, R_3)\}), \\ & (4, 16, \{(L_2, R_1), (L_3, R_2)\}), (4, 23, \{(L_2, R_1), (L_3, R_3), (R_0, R_2)\}), \\ & (4, 10, \{(L_2, R_1), (L_3, R_2)\}), (4, 30, \{(L_2, R_0), (L_3, R_1)\}), \\ & (4, 13, \{(L_2, R_3), (L_3, R_2), (R_0, R_1)\}), (4, 33, \{(L_2, R_2), (L_3, R_1), (R_0, R_3)\}), \\ & (4, 33, \{(L_2, R_1), (L_3, R_3), (R_0, R_2)\}), (4, 33, \{(L_2, R_3), (L_3, R_2), (R_0, R_1)\}), \\ & (4, 32, \{(L_2, R_1), (L_3, R_2)\})\} \\ \xi_4 = \{ & (4, 32, \{(L_2, R_2), (L_3, R_1)\}), (4, 30, \{(L_2, R_1), (L_3, R_0)\}), \\ & (4, 26, \{(L_2, R_3), (L_3, R_0)\}), (4, 11, \{(L_2, R_2), (L_3, R_3)\}), \\ & (4, 27, \{(L_2, R_1), (L_3, R_2), (R_0, R_3)\}), (4, 16, \{(L_2, R_2), (L_3, R_1)\}), \\ & (4, 4, \{(L_2, R_1), (L_3, R_0)\}), (4, 23, \{(L_2, R_3), (L_3, R_1), (R_0, R_2)\}), \\ & (4, 10, \{(L_2, R_2), (L_3, R_1)\}), (4, 13, \{(L_2, R_2), (L_3, R_3), (R_0, R_1)\}), \\ & (4, 33, \{(L_2, R_1), (L_3, R_2), (R_0, R_3)\}), (4, 33, \{(L_2, R_3), (L_3, R_1), (R_0, R_2)\}), \\ & (4, 33, \{(L_2, R_2), (L_3, R_3), (R_0, R_1)\})\} \\ \xi_5 = \{ & (4, 22, \{(L_2, L_3)\})\} \\ \xi_6 = \{ & (4, 7, \{(L_2, L_3), (R_0, R_3)\})\} \\ \xi_7 = \{ & (4, 19, \{(L_2, L_3), (R_2, R_3)\})\} \\ \xi_8 = \{ & (4, 1, \{(L_2, L_3), (R_0, R_3), (R_1, R_2)\})\} \\ \xi_9 = \{ & (4, 16, \{(L_2, L_3), (R_1, R_2)\}), (4, 4, \{(L_2, L_3), (R_0, R_1)\}), \\ & (4, 26, \{(L_2, L_3), (R_0, R_3)\}), (4, 11, \{(L_2, L_3), (R_2, R_3)\}), \\ & (4, 27, \{(L_2, L_3), (R_0, R_3), (R_1, R_2)\}), (4, 23, \{(L_2, L_3), (R_0, R_2), (R_1, R_3)\}), \\ & (4, 10, \{(L_2, L_3), (R_1, R_2)\}), (4, 30, \{(L_2, L_3), (R_0, R_1)\}), \\ & (4, 13, \{(L_2, L_3), (R_0, R_1), (R_2, R_3)\}), (4, 33, \{(L_2, L_3), (R_0, R_3), (R_1, R_2)\}), \\ & (4, 33, \{(L_2, L_3), (R_0, R_2), (R_1, R_3)\}), (4, 33, \{(L_2, L_3), (R_0, R_1), (R_2, R_3)\}), \\ & (4, 32, \{(L_2, L_3), (R_1, R_2)\})\}, \end{aligned}\] where \(\xi_4\) is the SCC we analyzed earlier, and \(v \in \xi_9\). The condensantion of \(\rho(v)\) (the resulting graph if each SCC is contracted to a single vertex) is shown in Figure 2.

The initial values in the source SCCs \(\xi_1\) and \(\xi_2\) are all zero, and they are deleted accordingly. \(\xi_3\) then becomes a source SCC, and since all the initial values are zero here as well, it is also deleted, and we are left with \[\xi_4 \longrightarrow \xi_5 \longrightarrow \xi_6 \longrightarrow \xi_7 \longrightarrow \xi_8 \longrightarrow \xi_9.\] We have just seen that the minimal universal characteristic polynomial on \(\xi_4\) is \(x^6-x^3-x-1\). \(\xi_9\) is isomorphic to \(\xi_4\), and therefore has the same minimal universal characteristic polynomial. The remaining SCCs are trivial, and this gives \(P^{(v)}(x)=(x^6-x^3-x-1)^2\).

Generally, checking divisors ought to be done after executing the flowchart like we did in the example with a single SCC.

5. Results

For \(k=3\), let the polynomials \(P^{(1)} \dotsc, P^{(8)}\) be given by \[\begin{aligned} P^{(1)}(x) & = x-1, \\ P^{(2)}(x) & = x+1, \\ P^{(3)}(x) & = x^2+1, \\ P^{(4)}(x) & = x^2-x+1, \\ P^{(5)}(x) & = x^2+x+1, \\ P^{(6)}(x) & = x^4-x^2+1, \\ P^{(7)}(x) & = x^6-x^3-x-1, \\ P^{(8)}(x) & = x^{14}-x^{12}-x^8+x^6-x^4-2x^2-1. \end{aligned}\]

Table 2 gives the minimal universal characteristic polynomials for each class of SCCs under graph isomorphism.

Algorithm 1 yields \[P(x)=P_1(x) P_2(x) P_3(x) P_4(x) P_5(x) P_6(x) \left(P_7(x)\right)^2 P_8(x),\] of degree 38 as a characteristic polynomial on \((\sigma_3, I_3)\), which we have verified to be minimal by checking all maximal divisors. The corresponding recurrence relation \[P_{38}u_n + P_{37}u_{n-1} + \dotsc + P_1 u_{n-37} + P_0 u_{n-38}=0,\] holds for each signature for \(n=45\), and thus, by Lemma 3.3, for all \(n \geq 45\). It follows that it holds for \(u_n=h_3(n)\) for \(n \geq 45\). However, we have \(h_3(1) = 1\) and \(h_3(2)=4\) and can verify that the recurrence relation also holds for \(39 \leq n < 45\), from which we can conclude that it holds for all \(n \geq 39\).

Similarly for \(k=4\), let \[\begin{aligned} Q^{(1)}(x) = & x-1, \\ Q^{(2)}(x) = & x+1, \\ Q^{(3)}(x) = & x^2+1, \\ Q^{(4)}(x) = & x^4+1, \\ Q^{(5)}(x) = & x^4-x^3+x^2-x+1, \\ Q^{(6)}(x) = & x^4+x^3+x^2+x+1, \\ Q^{(7)}(x) = & x^8-x^6+x^4-x^2+1, \\ Q^{(8)}(x) = & x^8-x^4-x^2+x-1, \\ Q^{(9)}(x) = & x^8-x^4-x^2-x-1, \\ Q^{(10)}(x) = & x^{10}+x^8-2x^6-x^4+x^2-1, \\ Q^{(11)}(x) = & x^{21}-x^{20}+x^{19}-2x^{18}+2x^{17}-3x^{16}+3x^{15}-3x^{14}+3x^{13}-3x^{12} \\ & +2x^{11}-2x^{10}+x^9-2x^8+2x^7-x^6+x^5-x^4+x^3-x^2+x-1, \\ Q^{(12)}(x) = & x^{22}-2x^{18}-x^{15}-2x^{14}-x^{12}+x^{11}+3x^{10}-x^9-x^8+2x^6+x^5+x^4-x^3+x+1, \\ Q^{(13)}(x) = & x^{37}+x^{34}-x^{29}+x^{27}-x^{25}+x^{20}+3x^{17}+3x^{14}+8x^{12}+x^9+3x^7-3x^5-1. \end{aligned}\]

Table 3 gives the minimal universal characteristic polynomials for each class of SCCs.

Again using Algorithm 1 and checking divisors, the minimal characteristic polynomial on \((\sigma_4, I_4)\) was found to be \[\begin{aligned} & \left(Q^{(1)}(x) Q^{(2)}(x) Q^{(3)}(x) Q^{(5)}(x) Q^{(6)}(x) Q^{(7)}(x) Q^{(11)}(x)\right)^2 \nonumber \\ & Q^{(4)}(x) Q^{(8)}(x) Q^{(9)}(x) Q^{(10)}(x) Q^{(12)}(x) Q^{(13)}(x), \end{aligned} \tag{13}\] of degree 171.

Let \[\begin{aligned} Q(x) = & Q^{(1)}(x) \left(Q^{(2)}(x) Q^{(3)}(x) Q^{(5)}(x) Q^{(7)}(x) Q^{(11)}(x) \right)^2 \\ & Q^{(4)}(x) Q^{(8)}(x) Q^{(9)}(x) Q^{(10)}(x) Q^{(12)}(x) Q^{(13)}(x), \end{aligned}\] of degree 162, such that (13) is equal to \[Q(x) Q^{(1)}(x) \left(Q^{(6)}(x)\right)^2.\]

There are only 25 signatures \((n_L, n_R, \lambda)\) for which \(Q(x) Q^{(1)}(x) Q^{(6)}(x)\) is not a characteristic polynomial for \(\{u^{(n_L, n_R, \lambda)}_n\}\) for \(n=176\), and none of them can reach any of the signatures corresponding to Hamiltonian cycles in \(G(n, 4)\). Therefore, \(Q(x) Q^{(1)}(x) Q^{(6)}(x)\) is a characteristic polynomial for \(h_4(n)\) for \(n \geq 176\) by Lemma 3.3, and since \(Q^{(1)}(x) Q^{(6)}(x) = x^5-1\), it follows that \[Q_{162}h_4(n) + Q_{161}h_4(n-1) + \dotsc + Q_1 h_4(n-161) + Q_0 h_4(n-162),\] is periodic with period 5, starting from \(n=171\). But all the first five terms are zero, and thus, \(Q(x)\) is a characteristic polynomial for \(h_4(n)\) for \(n \geq 171\). Moreover, with \(h_4(1)=1\), \(h_4(2)=0\) and \(h_4(3)=3\), we can verify that the recurrence relation also holds for \(163 \leq n < 171\) and conclude that it holds for all \(n \geq 163\).

Appendix A gives the initial values of \(h_3(n)\), \(h_4(n)\) and the coefficients of \(P(x)\) and \(Q(x)\).

It might be desirable to write \(h_k(n)\) as a sum of the \(n\)th terms of several recursive sequences, each with a characteristic polynomial of relatively small degree. One possible first step is to distinguish between admissible subgraphs of \(G'(n, k)\) with an even and an odd number of loose ends on each side. Partitioning the graph of signatures \(\sigma_k\) into \(\sigma^{(e)}_k\) and \(\sigma^{(o)}_k\) accordingly, we can replace (2) by \[h^{(e)}_k(n) = \sum_{(n_L, n_R, \lambda) \in H_k \cap V \left( \sigma^{(e)}_3 \right)} u^{(n_L, n_R, \lambda)}_n,\] and \[h^{(o)}_k(n) = \sum_{(n_L, n_R, \lambda) \in H_k \cap V \left( \sigma^{(o)}_3 \right) } u^{(n_L, n_R, \lambda)}_n,\] such that \(h_k(n) = h^{(e)}_k(n) + h^{(o)}_k(n)\). Furthermore, as touched upon when we considered characteristic polynomials for \(h_4(n)\) above, a divisor of the characteristic polynomial of the form (or dividing) \(x^j-1\) can be eliminated if we introduce a periodic function of period \(j\) on the right hand side of the recurrence relation.

Here is a brief summary of how this plays out for \(k=3\). \(V \left( \sigma^{(e)}_3 \right)\) consists of signatures with \(n_L, n_R \in \{1, 4, 6, 7, 10, \dotsc\}\) (confer Table 1). With the same analysis as before, we obtain the initial values \(1, 2, 0, 0, 0, 8, 7, 0, 9, 12, 11, 36\) of \(h_k^{(e)}(n)\) for \(1 \leq n \leq 12\), and the recurrence relation \[\begin{split} h_k^{(e)}(n) – 2h_k^{(e)}(n-3) – 2h_k^{(e)}(n-5)\\- h_k^{(e)}(n-6) + 2h_k^{(e)}(n-8) + 2h_k^{(e)}(n-9)\\+ h_k^{(e)}(n-10) + 2h_k^{(e)}(n-11) + h_k^{(e)}(n-12) \end{split}= \begin{cases} 8 &\quad\text{if }n \equiv 2 (\operatorname{mod} 4)\\ 0 &\quad\text{otherwise} \end{cases}\] for \(n \geq 13\). A periodic function satisfying the same recurrence relation is given by \[u^{(e)}_n= \begin{cases} 2 &\quad\text{if }n \equiv 2 (\operatorname{mod} 4)\\ 0 &\quad\text{otherwise.} \end{cases}\]

Similarly, \(V \left( \sigma^{(o)}_3 \right)\) consists of signatures with \(n_L, n_R \in \{2, 3, 5, 8, 9, \dotsc\}\), the initial values of \(h_k^{(o)}(n)\) for \(1 \leq n \leq 14\) are \(0, 2, 0, 6, 0, 8, 0, 6, 0, 12, 0, 32, 0, 58\), and \[\begin{split} h_k^{(o)}(n) – h_k^{(o)}(n-2) – h_k^{(o)}(n-6)\\+ h_k^{(o)}(n-8) – h_k^{(o)}(n-10)\\- 2h_k^{(o)}(n-12) – h_k^{(o)}(n-14) \end{split}= \begin{cases} 16 &\quad\text{if }n \equiv 0 \text{ or } 2 (\operatorname{mod} 12)\\ -16 &\quad\text{if }n \equiv 8 (\operatorname{mod} 12)\\ 0 &\quad\text{otherwise} \end{cases}\] for \(n \geq 15\). A periodic function satisfying the same recurrence relation is given by \[u^{(o)}_n= \begin{cases} -12 &\quad\text{if }n \equiv 0 (\operatorname{mod} 4)\\ 4 &\quad\text{if }n \equiv 4 \text{ or }8 (\operatorname{mod}12)\\ 0 &\quad\text{otherwise.} \end{cases}\]

Thus, taking \(h_3^{(\alpha)}(n) = h_k^{(e)}(n) – u^{(e)}_n\), \(h_3^{(\beta)}(n) = h_k^{(o)}(n) – u^{(o)}_n\) and \(h_3^{(\gamma)}(n) = u^{(e)}_n + u^{(o)}_n\) leads to the following alternative to Theorem 5.1 for \(k=3\).

Conflicts of interest

The author declares that he has no conflicts of interest.

Appendix A: Initial values for \(h_3(n)\) and \(h_4(n)\) and coefficients of their characteristic polynomials