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

%I #36 Mar 12 2024 22:52:14

%S 1,4,4,4,5,8,13,14,14,16,22,24,29,33,36,40,47,52,58,63,68

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

%D 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 Andy Huchala, <a href="/A342576/a342576.py.txt">Python program</a>.

%H Robert Israel, <a href="/A342576/a342576.pdf">Optimal configurations for n = 3 to 14</a>

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

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

%p f:= proc(N)

%p local verts,Rverts,edg,cons,i,j,e;

%p verts:= [seq(seq([i,j],i=1..N),j=1..N)]:

%p for i from 1 to N^2 do Rverts[op(verts[i])]:= i od:

%p edg:= {seq(seq({Rverts[i,j],Rverts[i+1,j+2]},i=1..N-1),j=1..N-2),

%p seq(seq({Rverts[i,j],Rverts[i+2,j+1]},i=1..N-2),j=1..N-1),

%p seq(seq({Rverts[i,j],Rverts[i+1,j-2]},i=1..N-1),j=3..N),

%p seq(seq({Rverts[i,j],Rverts[i+2,j-1]},i=1..N-2),j=2..N)}:

%p cons:= {seq(x[e[1]]+x[e[2]]<=1, e=edg),

%p seq(x[i]+add(`if`(member({i,j},edg),x[j],0),j=1..N^2)>=1, i=1..N^2)}:

%p Optimization:-Minimize(add(x[i],i=1..N^2),cons,assume=binary)[1]

%p end proc:

%p map(f, [$1..13]); # _Robert Israel_, Mar 17 2021

%Y Cf. A006075, A075324, A299029, A279404, A030978.

%K nonn,more

%O 1,2

%A _Andrey Zabolotskiy_, Mar 15 2021

%E a(11) to a(14) from _Robert Israel_, Mar 17 2021

%E a(15)-a(18) from _Eric W. Weisstein_, Aug 01 2023

%E a(19) from _Eric W. Weisstein_, Jan 14 2024

%E a(20)-a(21) from _Andy Huchala_, Mar 10 2024