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

1, 1, 10, 31, 172, 2253, 50652, 900243, 26990541, 1534414257

Offset

1,3

Links

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

Eric Weisstein's World of Mathematics, Knight Graph.

Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set.

Eric Weisstein's World of Mathematics, Minimal Vertex Cover.

Mathematica

Table[Length[FindIndependentVertexSet[KnightTourGraph[n, n], Infinity, All]], {n, 7}]

Prog

(Python)
from networkx import empty_graph, find_cliques, complement
def A289201(n):
    G = empty_graph((i, j) for i in range(n) for j in range(n))
    G.add_edges_from(((i, j), (i+k, j+l)) for i in range(n) for j in range(n) for (k, l) in ((1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)) if 0<=i+k<n and 0<=j+l<n)
    return sum(1 for c in find_cliques(complement(G))) # Chai Wah Wu, Jan 11 2024

Crossrefs

Cf. A141243, A289203, A287071, A289200.

Sequence in context: A161325 A187705 A267564 * A042849 A097236 A332254

Adjacent sequences: A289198 A289199 A289200 * A289202 A289203 A289204

Keyword

nonn,more

Author

Eric W. Weisstein, Jun 28 2017

Extensions

a(9)-a(10) from Andrew Howroyd, Jul 01 2017

Status

approved