A378763 - OEIS

%I #24 Dec 19 2024 13:47:08

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

%N Lower matching number for the n X n torus grid graph.

%C a(18) = 108.

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

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

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/LowerMatchingNumber.html">Lower Matching Number</a>.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/TorusGridGraph.html">Torus Grid Graph</a>.

%F 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

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

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

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

%K nonn,more,hard

%O 3,1

%A _Eric W. Weisstein_, Dec 06 2024