A222197 -id:A222197 - cp's OEIS frontend

A222199 Number of Hamiltonian cycles in the graph C_n X C_n.

48, 1344, 23580, 3273360, 257165468, 171785923808, 61997157648756, 196554899918485160

Offset: 3

N. J. A. Sloane, Feb 14 2013

C_n X C_n is also known as the (n,n)-torus grid graph.

Artem M. Karavaev, Hamilton Cycles.
Eric Weisstein's World of Mathematics, Hamiltonian Cycle.
Eric Weisstein's World of Mathematics, Torus Grid Graph.

Cf. A270273, A003763, A222197, A268838, A222198, A193153, A270247.

Table[Length[FindHamiltonianCycle[GraphProduct[CycleGraph[n], CycleGraph[n], "Cartesian"], All]], {n, 3, 6}] (* Eric W. Weisstein, Dec 16 2023 *)

A359855 Array read by antidiagonals: T(n,k) is the number of Hamiltonian cycles in the stacked prism graph P_n X C_k, n >= 1, k >= 2.

Original entry on oeis.org

1, 1, 4, 1, 3, 4, 1, 6, 6, 4, 1, 5, 22, 12, 4, 1, 8, 30, 82, 24, 4, 1, 7, 86, 160, 306, 48, 4, 1, 10, 126, 776, 850, 1142, 96, 4, 1, 9, 318, 1484, 7010, 4520, 4262, 192, 4, 1, 12, 510, 6114, 18452, 63674, 24040, 15906, 384, 4, 1, 11, 1182, 12348, 126426, 229698, 578090, 127860, 59362, 768, 4

Offset: 1

Andrew Howroyd, Feb 18 2025

The case for P_n X C_2 is determined using a double edge for C_2.

			Array begins:
=========================================================
n\k | 2   3     4      5       6        7          8 ...
----+---------------------------------------------------
  1 | 1   1     1      1       1        1          1 ...
  2 | 4   3     6      5       8        7         10 ...
  3 | 4   6    22     30      86      126        318 ...
  4 | 4  12    82    160     776     1484       6114 ...
  5 | 4  24   306    850    7010    18452     126426 ...
  6 | 4  48  1142   4520   63674   229698    2588218 ...
  7 | 4  96  4262  24040  578090  2861964   53055038 ...
  8 | 4 192 15906 127860 5247824 35663964 1087362018 ...
   ...

Eric Weisstein's World of Mathematics, Hamiltonian Cycle.
Eric Weisstein's World of Mathematics, Stacked Prism Graph.

Columns 2..12 are A123932(n-1), A003945(n-1), A003699, A003731, A180582, A180583, A180584, A180585, A180586, A180587, A180588.
Rows 1..2 are A000012, A103889(n+1).
Cf. A222196 (order of recurrences), A222197 (main diagonal), A270273, A321172.

A268894 Number of Hamiltonian paths in C_n X P_n.

Original entry on oeis.org

1, 4, 144, 4016, 152230, 14557092, 1966154260, 761411682704, 411068703517542, 684434716944151900, 1572754514153890134760, 11579615738168536799184984, 117186519917858266359631481672, 3877921919790491112398750141807648, 176258463464553583688099296874564393850, 26493868301658838913487471166447301509560736

Offset: 1

Andrew Howroyd, Feb 15 2016

nonn

This is the number of undirected paths.

Artem M. Karavaev, Hamilton Paths
Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Stacked Prism Graph

Cf. A003763, A222197, A120443, A268838.

Cf. A003752, A003732.

A339140 Number of (undirected) cycles in the graph C_n X P_n.

Original entry on oeis.org

6, 63, 1540, 119235, 29059380, 21898886793, 50826232189144, 361947451544923557, 7884768474166076906420, 524518303312357729182869149, 106448798893410608983300257207398, 65866487708413725073741586390176988083, 124207126413825808953168887580780401519104028

Offset: 2

Seiichi Manyama, Nov 25 2020

nonn

			If we represent each vertex with o, used edges with lines and unused edges with dots, and repeat the wraparound edges on left and right, the a(2) = 6 solutions for n = 2 are:
    .o-o.   -o.o-   .o-o.   -o.o-   -o-o-   .o.o.
     | |     | |     | |     | |     . .     . .
    .o-o.   .o-o.   -o.o-   -o.o-   .o.o.   -o-o-

Ed Wynn, Table of n, a(n) for n = 2..18
Eric Weisstein's World of Mathematics, Graph Cycle

Cf. A140517, A222197, A296527, A339136, A339137, A339142, A339143.

# Using graphillion
from graphillion import GraphSet
def make_CnXPk(n, k):
    grids = []
    for i in range(1, k + 1):
        for j in range(1, n):
            grids.append((i + (j - 1) * k, i + j * k))
        grids.append((i + (n - 1) * k, i))
    for i in range(1, k * n, k):
        for j in range(1, k):
            grids.append((i + j - 1, i + j))
    return grids
def A339140(n):
    universe = make_CnXPk(n, n)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles()
    return cycles.len()
print([A339140(n) for n in range(3, 7)])

a(10) and a(12) from Seiichi Manyama, Nov 25 2020

a(2), a(9), a(11) and a(13)-a(18) from Ed Wynn, Jun 25 2023

cp's OEIS Frontend

A222199 Number of Hamiltonian cycles in the graph C_n X C_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A359855 Array read by antidiagonals: T(n,k) is the number of Hamiltonian cycles in the stacked prism graph P_n X C_k, n >= 1, k >= 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A268894 Number of Hamiltonian paths in C_n X P_n.

Views

Author

Keywords

Comments

Links

Crossrefs

A339140 Number of (undirected) cycles in the graph C_n X P_n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Extensions