A378763 Lower matching number for the n X n torus grid graph.

3, 6, 9, 12, 17, 22, 27, 34, 42, 48, 58, 67, 75, 87

Offset: 3

Author

Eric W. Weisstein, Dec 06 2024

Keywords

• nonn
• more
• hard

Comments

a(18) = 108.

Seems to be either A008810(n) = ceil(n^2/3) or A008810(n)+1.

For known terms, a(n) is one more than A008810(n) for n = 11, 13, 14, 16.

Links

• Eric Weisstein's World of Mathematics, Lower Matching Number.
• Eric Weisstein's World of Mathematics, Torus Grid Graph.

Crossrefs

Cf. A008810 (ceil(n^2/3)).

Cf. A280984 (lower matching number for the n X n grid graph).

Programs

Mathematica

Table[Min[Length /@ FindIndependentVertexSet[LineGraph @ GraphProduct[CycleGraph[n], CycleGraph[n], "Cartesian"], Infinity, All]], {n, 3, 5}]

Formula

a(n) = n^2/3 if 3|n, otherwise a(n) >= A008810(n). [Proof: let the [minimum] maximal independent edge set be E. Let b be the number of edges between two vertices incident to different edges from E. The total number of edges connecting a vertex incident to an edge from E and a vertex not incident to any edge from E is equal to 4(n^2-2a(n)) but also to 6a(n)-2b; equalising these, we find b = 7a(n)-2n^2. Also, a(n) <= b, which gives the desired inequality a(n) >= n^2/3.] - Andrey Zabolotskiy, Dec 19 2024