cp's OEIS Frontend

A342576 Independent domination number for knight graph on an n X n board.

%I A342576 #36 Mar 12 2024 22:52:14
%S A342576 1,4,4,4,5,8,13,14,14,16,22,24,29,33,36,40,47,52,58,63,68
%N A342576 Independent domination number for knight graph on an n X n board.
%D A342576 Sandra M. Hedetniemi, Stephen T. Hedetniemi, Robert Reynolds, Combinatorial Problems on Chessboards: II, in: Domination in Graphs - Advanced Topics, Marcel Dekker, 1998. See p. 141.
%H A342576 Andy Huchala, <a href="/A342576/a342576.py.txt">Python program</a>.
%H A342576 Robert Israel, <a href="/A342576/a342576.pdf">Optimal configurations for n = 3 to 14</a>
%H A342576 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/KnightGraph.html">Knight Graph</a>.
%H A342576 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/LowerIndependenceNumber.html">Lower Independence Number</a>.
%p A342576 f:= proc(N)
%p A342576   local verts,Rverts,edg,cons,i,j,e;
%p A342576   verts:= [seq(seq([i,j],i=1..N),j=1..N)]:
%p A342576   for i from 1 to N^2 do Rverts[op(verts[i])]:= i od:
%p A342576   edg:= {seq(seq({Rverts[i,j],Rverts[i+1,j+2]},i=1..N-1),j=1..N-2),
%p A342576        seq(seq({Rverts[i,j],Rverts[i+2,j+1]},i=1..N-2),j=1..N-1),
%p A342576        seq(seq({Rverts[i,j],Rverts[i+1,j-2]},i=1..N-1),j=3..N),
%p A342576        seq(seq({Rverts[i,j],Rverts[i+2,j-1]},i=1..N-2),j=2..N)}:
%p A342576   cons:= {seq(x[e[1]]+x[e[2]]<=1, e=edg),
%p A342576     seq(x[i]+add(`if`(member({i,j},edg),x[j],0),j=1..N^2)>=1, i=1..N^2)}:
%p A342576   Optimization:-Minimize(add(x[i],i=1..N^2),cons,assume=binary)[1]
%p A342576 end proc:
%p A342576 map(f, [$1..13]); # _Robert Israel_, Mar 17 2021
%Y A342576 Cf. A006075, A075324, A299029, A279404, A030978.
%K A342576 nonn,more
%O A342576 1,2
%A A342576 _Andrey Zabolotskiy_, Mar 15 2021
%E A342576 a(11) to a(14) from _Robert Israel_, Mar 17 2021
%E A342576 a(15)-a(18) from _Eric W. Weisstein_, Aug 01 2023
%E A342576 a(19) from _Eric W. Weisstein_, Jan 14 2024
%E A342576 a(20)-a(21) from _Andy Huchala_, Mar 10 2024