login
A289201
Number of maximal independent vertex sets (and minimal vertex covers) in the n X n knight graph.
1
1, 1, 10, 31, 172, 2253, 50652, 900243, 26990541, 1534414257
OFFSET
1,3
LINKS
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
KEYWORD
nonn,more
AUTHOR
Eric W. Weisstein, Jun 28 2017
EXTENSIONS
a(9)-a(10) from Andrew Howroyd, Jul 01 2017
STATUS
approved