A297486 Number of maximal matchings in the n X n torus grid graph.

84, 2000, 205920, 39187952, 21856506798, 32510786132592, 124523589644006520

Offset

3,1

Links

Table of n, a(n) for n=3..9.

Eric Weisstein's World of Mathematics, Matching

Eric Weisstein's World of Mathematics, Maximal Independent Edge Set

Eric Weisstein's World of Mathematics, Torus Grid Graph

Mathematica

a[n_] := Module[{maxCycle, addition, basis, compatibleQ},
   maxCycle =
    Select[Tuples[{0, 1}, n],
     And[#*RotateRight[#] == ConstantArray[0, n],
       AllTrue[# + RotateRight[#] + RotateLeft[#], # > 0 &]] &];
   addition[s_] :=
    With[{G =
       RelationGraph[And[#1 != #2, AllTrue[#1 - #2, NonNegative]] &,
        DeleteDuplicates[
         Map[
          ReplacePart[#,
            Map[Rule[#, 0] &,
             Complement[Range[n],
              Flatten[Position[s + RotateLeft[s], 0]]]]] &,
          maxCycle]]]},
     Map[{s, #} &, Pick[VertexList[G], VertexInDegree[G], 0]]
     ];
   basis = Flatten[Map[addition, Tuples[{0, 1, 2}, n]], 1];
   compatibleQ[{s_, t_}, {p_, q_}] :=
    And[Position[s, 2] == Position[p, 1],
     AllTrue[
      t + RotateRight[t] + q + RotateRight[q] + s + p, # > 0 &]];
   Tr[MatrixPower[
     SparseArray[
      Table[
       Boole[compatibleQ[tup1, tup2]], {tup1, basis}, {tup2, basis}]],
      n]]
   ];
Table[a[n], {n, 3, 6}] (* Pjotr Buys, Jul 06 2023 *)
Table[Length@FindIndependentVertexSet[LineGraph@GraphProduct[CycleGraph[n], CycleGraph[n], "Cartesian"], Infinity, All], {n, 3, 5}] (* Eric W. Weisstein, Jan 25 2024 *)

Crossrefs

Sequence in context: A358864 A098935 A370572 * A104674 A221010 A219584

Adjacent sequences: A297483 A297484 A297485 * A297487 A297488 A297489

Keyword

nonn,more

Author

Eric W. Weisstein, Dec 30 2017

Extensions

a(6) from Andrew Howroyd, Dec 30 2017

a(7) from Pontus von Brömssen, Dec 31 2022

a(8)-a(9) from Pjotr Buys, Jul 06 2023

Status

approved