login
A297486
Number of maximal matchings in the n X n torus grid graph.
0
84, 2000, 205920, 39187952, 21856506798, 32510786132592, 124523589644006520
OFFSET
3,1
LINKS
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
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