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,2

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

Table of n, a(n) for n=1..21.

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.

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

Crossrefs

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

Sequence in context: A342348 A127932 A006075 * A370389 A241295 A074904

Adjacent sequences: A342573 A342574 A342575 * A342577 A342578 A342579

Keyword

nonn,more

Author

Andrey Zabolotskiy, Mar 15 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

Status

approved