A299029 -id:A299029 - cp's OEIS frontend

A321684 Independent domination number of the n X n grid graph.

0, 1, 2, 3, 4, 7, 10, 12, 16, 21, 24, 30, 35, 40, 47, 53, 60, 68, 76, 84, 92, 101, 111, 121, 131, 141, 152, 164, 176, 188, 200, 213, 227, 241, 255, 269, 284, 300, 316, 332, 348, 365, 383, 401, 419, 437, 456, 476, 496, 516, 536, 557, 579, 601, 623, 645, 668

Offset: 0

Andrey Zabolotskiy, Jan 14 2019

Colin Barker, Table of n, a(n) for n = 0..1000
Simon Crevals, Patric R. J. Östergård, Independent domination of grids, Discrete Math., 338 (2015), 1379-1384.
Index entries for linear recurrences with constant coefficients, signature (2,-1,0,0,1,-2,1).

Cf. A104519, A075324, A299029, A279404, A291297.

ogf := (-41*x^6 + 47*x^5 - x^3 - x^2 + 41*x - 47)/((x - 1)^3*(x^4 + x^3 + x^2 + x + 1)): ser := series(ogf, x, 44):
(0,1,2,3,4,7,10,12,16,21,24,30,35,40), seq(coeff(ser, x, n), n=0..42); # Peter Luschny, Jan 14 2019

concat(0, Vec(x*(1 + 2*x^4 - x^5 - x^6 + 2*x^7 + x^8 - 4*x^9 + 3*x^10 - 2*x^12 + x^13 + x^14 - 2*x^15 + 2*x^16 - 2*x^18 + x^19) / ((1 - x)^3*(1 + x + x^2 + x^3 + x^4)) + O(x^40))) \\ Colin Barker, Jan 14 2019

For n >= 14, a(n) = floor((n+2)^2 / 5 - 4).
a(n) = A104519(n+2), the domination number of the n X n grid graph, for all n except for n = 9, 11.
From Colin Barker, Jan 14 2019: (Start)
G.f.: x*(1 + 2*x^4 - x^5 - x^6 + 2*x^7 + x^8 - 4*x^9 + 3*x^10 - 2*x^12 + x^13 + x^14 - 2*x^15 + 2*x^16 - 2*x^18 + x^19) / ((1 - x)^3*(1 + x + x^2 + x^3 + x^4)).
a(n) = 2*a(n-1) - a(n-2) + a(n-5) - 2*a(n-6) + a(n-7) for n > 20.
(End)

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

Original entry on oeis.org

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

Offset: 1

Andrey Zabolotskiy, Mar 15 2021

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.

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.

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

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

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

cp's OEIS Frontend

A321684 Independent domination number of the n X n grid graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula