Hamilton Cycles
Lattice Pm×Pn
Recurrence
a[n] is the number of hamilton cycles (n = 1, 2, …).
The number of Hamilton cycles in product lattice graph is a linear recurrence. We distinguish odd and even values of m. If m is odd, then we take in mind graph Pm×P2n. For example, if m=3, the recurrence for the number of Hamilton cycles in P3×P2n is given by
init = [1];
a[n] = 2*a[n-1].
If m=4, the recurrence for P4×Pn is given by
init = [0, 1, 2, 6];
a[n] = a[n-4] – 2*a[n-3] + 2*a[n-2] + 2*a[n-1].
The table below shows the order of known recurrences.
Our result: m=10 (May, 2009).
Our result: m=11 (August, 2010).
from m=12 to m=14 (January, 2011).
| m | Order | Links | |
|---|---|---|---|
| 3 | 1 | ||
| 4 | 4 | OEIS::A006864 | |
| 5 | 3 | OEIS::A006865 | |
| 6 | 14 | OEIS::A145401 | |
| 7 | 18 | OEIS::A145416 | |
| 8 | 66 | OEIS::A145418 | |
| 9 | 104 | OEIS::A160149 | |
| 10 | 346 | OEIS::A180504 | |
| 11 | 671 | OEIS::A180505 | |
| 12 | 2086 | ||
| 13 | 4479 | ||
| 14 | 13523 |
Maple Program
You may download (zip, 482 Kb) Maple programs which calculate the number of Hamilton cycles using known recurrence for m=3..11. Other recurrences and denominators of generating functions are here (zip, 35 Mb).
Also you can download (zip, 8767 Kb) files with the number of Hamilton cycles on Pm×Pn up to m=22 and n=100.
Square Grid (m=n)
Link: OEIS::A003763.
| n | The Number of Hamilton Cycles in P2n×P2n |
|---|---|
| 1 | 1 |
| 2 | 6 |
| 3 | 1072 |
| 4 | 4638576 |
| 5 | 467260456608 |
| 6 | 1076226888605605706 |
| 7 | 56126499620491437281263608 |
| 8 | 65882516522625836326159786165530572 |
| 9 | 1733926377888966183927790794055670829347983946 |
| 10 | 1020460427390768793543026965678152831571073052662428097106 |
| 11 | 13404209505893761748339786653564937498745897123531041248680272448954956 |
| 12 | ? |
Thin Cylinder Cm×Pn
Recurrence
a[n] is the number of hamilton cycles (n = 1, 2, …).
The number of Hamilton cycles in thin cylinder is a linear recurrence. But the case of n=1 is a special case (the answer is 1), so the recurrences start to work from n=2. For example, if m=3, the recurrence for the number of Hamilton cycles in C3×Pn is given by
init = [1,3];
a[n] = 2*a[n-1].
Explicit formula for n≥3:
a[n] = 3⋅2n-2,
The table below shows the order of known recurrences.
Our result: from m=6 to m=12 (August, 2010).
Our result: from m=13 to m=16 (January, 2011).
| m | Order | Links | |
|---|---|---|---|
| 3 | 1 | ||
| 4 | 2 | OEIS::A003699 | |
| 5 | 3 | OEIS::A003731 | |
| 6 | 7 | OEIS::A180582 | |
| 7 | 12 | OEIS::A180583 | |
| 8 | 20 | OEIS::A180584 | |
| 9 | 51 | OEIS::A180585 | |
| 10 | 74 | OEIS::A180586 | |
| 11 | 246 | OEIS::A180587 | |
| 12 | 303 | OEIS::A180588 | |
| 13 | 1320 | ||
| 14 | 1514 | ||
| 15 | 7936 | ||
| 16 | 8363 |
Maple Program
You may download (zip, 110 Kb) Maple programs which calculate the number of Hamilton cycles using known recurrence for m=3..12. Other recurrences and denominators of generating functions are here (zip, 23 Mb).
Also you can download (zip, 4496 Kb) files with the number of Hamilton cycles on Cm×Pn up to m=22 and n=100.
Square Cylinder (m=n)
.
| n | The Number of Hamilton Cycles in Cn×Pn |
|---|---|
| 3 | 6 |
| 4 | 82 |
| 5 | 850 |
| 6 | 63674 |
| 7 | 2861964 |
| 8 | 1087362018 |
| 9 | 218915964618 |
| 10 | 404126474166012 |
| 11 | 374905251599545986 |
| 12 | 3300767481388100805696 |
| 13 | 14292173292228195059141732 |
| 14 | 595370485568270695379595524706 |
| 15 | 12097705655943392593368119042729446 |
| 16 | 2376002864597357261596276659315012706002 |
| 17 | 227092183804629590129597176335482393366366980 |
| 18 | 209933491966125607144648831410536614852458041473076 |
| 19 | 94474812956197947992480226208710479658180360340376500012 |
| 20 | 410757088150304735846252847002210378296717918241103888685380494 |
| 21 | 870736199238806664768578299919651140322813738369460849338166193423684 |
| 22 | 17798323505323302622023838999698451905090684982867331529538127713385113122212 |
Torus Cm×Cn
Recurrence
a[n] is the number of hamilton cycles (n = 1, 2, …).
The number of Hamilton cycles in torus is a linear recurrence. The recurrences start to work from n=3. For example, if m=3, the recurrence for the number of Hamilton cycles in C3×Cn is given by
init = [48,126,390,1014,2982,8094];
a[n] = 5*a[n-1]-a[n-2]-25*a[n-3]+26*a[n-4]+20*a[n-5]-24*a[n-6].
Also we have an explicit foumula:
3n + 3/4⋅n⋅2n +(2n-(-2)n)/2+(-1)n-4
The table below shows the order of known recurrences.
Our result: from m=3 to m=8 (March, 2011).
| m | Order | Links | |
|---|---|---|---|
| 3 | 6 | ||
| 4 | 28 | ||
| 5 | 84 | ||
| 6 | 257 | ||
| 7 | 856 | ||
| 8 | 2785 |
Square Torus (m=n)
.
| n | The Number of Hamilton Cycles in Cn×Cn |
|---|---|
| 3 | 48 |
| 4 | 1344 |
| 5 | 23580 |
| 6 | 3273360 |
| 7 | 257165468 |
| 8 | 171785923808 |
| 9 | 61997157648756 |
| 10 | 196554899918485160 |
All factored denominators of generating functions are here (zip, 16 Kb).
Also you can download (zip, 22 Мb) files with the number of Hamilton cycles on Cm×Pn up to m=10 and n=3..500.