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

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

Offset: 1

Author

Andrey Zabolotskiy, Mar 15 2021

Keywords

• nonn
• more

References

• 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.

Links

• Andy Huchala, Python program.
• Robert Israel, Optimal configurations for n = 3 to 14
• Eric Weisstein's World of Mathematics, Knight Graph.
• Eric Weisstein's World of Mathematics, Lower Independence Number.

Crossrefs

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

Programs

Maple

f:= proc(N)
  local verts,Rverts,edg,cons,i,j,e;
  verts:= [seq(seq([i,j],i=1..N),j=1..N)]:
  for i from 1 to N^2 do Rverts[op(verts[i])]:= i od:
  edg:= {seq(seq({Rverts[i,j],Rverts[i+1,j+2]},i=1..N-1),j=1..N-2),
       seq(seq({Rverts[i,j],Rverts[i+2,j+1]},i=1..N-2),j=1..N-1),
       seq(seq({Rverts[i,j],Rverts[i+1,j-2]},i=1..N-1),j=3..N),
       seq(seq({Rverts[i,j],Rverts[i+2,j-1]},i=1..N-2),j=2..N)}:
  cons:= {seq(x[e[1]]+x[e[2]]<=1, e=edg),
    seq(x[i]+add(`if`(member({i,j},edg),x[j],0),j=1..N^2)>=1, i=1..N^2)}:
  Optimization:-Minimize(add(x[i],i=1..N^2),cons,assume=binary)[1]
end proc:
map(f, [$1..13]); # Robert Israel, Mar 17 2021

Extensions

a(11) to a(14) from Robert Israel, Mar 17 2021

a(15)-a(18) from Eric W. Weisstein, Aug 01 2023

a(19) from Eric W. Weisstein, Jan 14 2024

a(20)-a(21) from Andy Huchala, Mar 10 2024