patternModerate
Number of Hamiltonian cycles on a Sierpiński graph
Viewed 0 times
numberhamiltoniangraphcyclessierpiński
Problem
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 s
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 s
Solution
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$.
Or you can in fact show that $\bar{N}(n) = 3N(n)/2$, resulting in $N(n+1) = 3N^3$.
Context
StackExchange Computer Science Q#10305, answer score: 11
Revisions (0)
No revisions yet.