Number of Hamiltonian cycles on a Sierpiński graph

Question

I am new to this forum and just a physicist who does this to keep his brain in shape, so please show grace if I do not use the most elegant language. Also please leave a comment, if you think other tags would be more appropriate.

I am trying to solve this problem for which I need to compute the number of Hamiltonian cycles $C(n)$ in the $n$th order Sierpinski-graph $S_n$. (Please also see the above link for the definition and pictures of Sierpinski-graphs)

I have found $C(n)$, but I must have messed up something, because my solution does not match the given value $C(5) = 71328803586048$. My argumentation consists of very basic thoughts, and I cannot find the mistake. Any help is greatly appreciated. Even if it seems lengthy, the thoughts become trivial if you look at the graphs while following.

(a) In a given graph $S_n$ call the outer corners $A,B,C$. Then I define the following quantities:

$N(n) := $ the number of Hamiltonian paths from $A$ to $C$.

$\bar{N}(n) := $ the number of paths from $A$ to $C$ which visit each node once except $B$.

I will also call such paths $N$- or $\bar{N}$-type paths in the following.

(b) It is easy to see that $N(n)=\bar{N}(n)$.

The reason is the following: Consider a $N$-type path. Starting at $A$ this path is of the form $(A,...,X_1,B,X_2,...,C)$. By replacing the segment $(X_1,B,X_2)$ by $(X_1,X_2)$ we obtain a $\bar{N}$-type path. This operation uniquely maps all $N$-type paths to $\bar{N}$-type paths.

(c) We derive the recursion $N(n+1)=2N(n)^3$.

Consider an $N$-type path from $A$ to $B$ and denote the subtriangles at the outer corners $A,B,C$ by $T_A,T_B,T_C$, respectively. It is clear that the $N$-type path will visit each subtriangle exactly once starting from $T_A$ over $T_B$ to $T_C$. Now consider the node $Z$ at which the subtriangles $T_A$ and $T_C$ touch. There are two possibilities, when this point is visited by the path, either (i) before leaving $T_A$ or (ii) after entering $T_C$. In these cases the three subpaths inside $T_A,T_B,T_C$ are of the types (i) $N,N,\bar{N}$ or (ii) $\bar{N},N,N$, respectively. With this in mind we can count

$N(n+1)=N(n)N(n)\bar{N}(n)+\bar{N}(n)N(n)N(n)$ and with (b) we arrive at the upper recursion.

(d) We solve the recursion (c) with $N(1)=1$ and obtain $N(n)=2^{3^0+3^1+...+3^{n-2}}$.

(e) Consider a Hamiltonian cycle in the graph $S_n$. As each of three subtriangles is connected to the others via two nodes only, it is clear that the cycle will enter each subtriangle exactly once via one connecting node, then "fill" it, an finally leave it via the other connecting node. Hence the Hamiltonian cycle in $S_n$ consists of three $N$-type subpaths in the subtriangles which all have the structure of $S_{n-1}$. We can conclude for the number of Hamiltonian cycles

$C(n) = N(n-1)^3$.

However it follows for $n=5$

$C(5) = N(4)^3 = 8192^3=549755813888 \neq 71328803586048$

where the latter should be obtained according to the problem page (link above).

Thanks again for any help or comments.

Answer 1

Nice idea! The problem seems to be in step $(b)$. Replacing $(X_1,B,X_2)$ in an $N$-path by $(X_1,X_2)$ gives an $\bar{N}$-path, but not every $\bar{N}$-path will contain $(X_1,X_2)$. So this is not a bijection. This only says $N(n) \leq \bar{N}(n)$.

Or you can in fact show that $\bar{N}(n) = 3N(n)/2$, resulting in $N(n+1) = 3N^3$.