A332347 -id:A332347 - cp's OEIS frontend

A332348 Number of maximal independent sets in the 3 X n king graph.

1, 2, 6, 8, 22, 40, 82, 176, 340, 722, 1450, 2966, 6096, 12362, 25384, 51728, 105698, 216074, 440962, 901396, 1840686, 3760232, 7681828, 15689962, 32053346, 65473214, 133745304, 273208346, 558081744, 1140024080, 2328745042, 4757002434, 9717279194, 19849727740

Offset: 0

Andrew Howroyd, Feb 10 2020

Andrew Howroyd, Table of n, a(n) for n = 0..500
Index entries for linear recurrences with constant coefficients, signature (1,2,1,-2,2,-2).

Row n=3 of A332347.

Vec((1 + x + 2*x^2 - 3*x^3 + 2*x^4 - 2*x^5)/(1 - x - 2*x^2 - x^3 + 2*x^4 - 2*x^5 + 2*x^6) + O(x^40))

a(n) = a(n-1) + 2*a(n-2) + a(n-3) - 2*a(n-4) + 2*a(n-5) - 2*a(n-6) for n >= 6.

G.f.: (1 + x + 2*x^2 - 3*x^3 + 2*x^4 - 2*x^5)/(1 - x - 2*x^2 - x^3 + 2*x^4 - 2*x^5 + 2*x^6).

A332349 Number of maximal independent sets in the 4 X n king graph.

Original entry on oeis.org

1, 3, 12, 22, 79, 194, 537, 1519, 4011, 11258, 30506, 83661, 229754, 627171, 1721547, 4710045, 12901630, 35342272, 96764537, 265067580, 725878627, 1988023833, 5444771405, 14911382924, 40839083772, 111846316151, 306317816028, 838924085421, 2297583803229, 6292480053823

Offset: 0

Andrew Howroyd, Feb 10 2020

Andrew Howroyd, Table of n, a(n) for n = 0..500
Index entries for linear recurrences with constant coefficients, signature (1,4,3,-4,6,-3,-6).

Row n=4 of A332347.

Vec((1 + 2*x + 5*x^2 - 5*x^3 + 4*x^4 - 3*x^5 - 6*x^6)/((1 - x)*(1 - 4*x^2 - 7*x^3 - 3*x^4 - 9*x^5 - 6*x^6)) + O(x^40))

a(n) = a(n-1) + 4*a(n-2) + 3*a(n-3) - 4*a(n-4) + 6*a(n-5) - 3*a(n-6) - 6*a(n-7) for n >= 7.

G.f.: (1 + 2*x + 5*x^2 - 5*x^3 + 4*x^4 - 3*x^5 - 6*x^6)/((1 - x)*(1 - 4*x^2 - 7*x^3 - 3*x^4 - 9*x^5 - 6*x^6)).

A350818 Array read by antidiagonals: T(m,n) is the number of maximum independent sets in the m X n king graph.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 4, 1, 1, 1, 3, 4, 4, 3, 1, 1, 1, 12, 1, 12, 1, 1, 1, 4, 8, 9, 9, 8, 4, 1, 1, 1, 32, 1, 79, 1, 32, 1, 1, 1, 5, 16, 16, 27, 27, 16, 16, 5, 1, 1, 1, 80, 1, 408, 1, 408, 1, 80, 1, 1, 1, 6, 32, 25, 81, 64, 64, 81, 25, 32, 6, 1

Offset: 0

Andrew Howroyd, Jan 17 2022

The maximum size of an independent set is the independence number which in the case of an m X n king graph is given by ceiling(m/2)*ceiling(n/2).

			Table begins:
=============================================
m\n | 0 1  2  3    4   5     6   7      8
----+----------------------------------------
  0 | 1 1  1  1    1   1     1   1      1 ...
  1 | 1 1  2  1    3   1     4   1      5 ...
  2 | 1 2  4  4   12   8    32  16     80 ...
  3 | 1 1  4  1    9   1    16   1     25 ...
  4 | 1 3 12  9   79  27   408  81   1847 ...
  5 | 1 1  8  1   27   1    64   1    125 ...
  6 | 1 4 32 16  408  64  3600 256  26040 ...
  7 | 1 1 16  1   81   1   256   1    625 ...
  8 | 1 5 80 25 1847 125 26040 625 281571 ...
  ...

Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Maximum Independent Vertex Set

Cf. A018807, A245013, A332347, A350815, A350819.

T(m,n) = T(n,m).
T(2*m+1, 2*n+1) = 1.
T(2*m, 2*n+1) = (1+m)^(1+n).
T(2*m, 2*n) = A350819(m, n).

A288956 Number of maximal independent vertex sets (and minimal vertex covers) in the n X n king graph.

Original entry on oeis.org

1, 4, 8, 79, 544, 8197, 201611, 6214593, 391918650, 32239887128, 4599025630995, 1018245217588836, 346578151637999287, 193445218205732588935, 165199496607694525364163, 226636538088997406396236072, 488063150616514603623041818756, 1655950305544572458601638523072809

Offset: 1

Eric W. Weisstein, Jun 20 2017

nonn

Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
Eric Weisstein's World of Mathematics, Minimal Vertex Cover

Main diagonal of A332347.

Cf. A197048 (grid graph), A063443 (independent sets), A193580, A133791 (dominating sets).

a(9)-a(18) from Andrew Howroyd, Jun 26 2017

cp's OEIS Frontend

A332348 Number of maximal independent sets in the 3 X n king graph.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A332349 Number of maximal independent sets in the 4 X n king graph.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A350818 Array read by antidiagonals: T(m,n) is the number of maximum independent sets in the m X n king graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A288956 Number of maximal independent vertex sets (and minimal vertex covers) in the n X n king graph.

Views

Author

Keywords

Links

Crossrefs

Extensions