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

Author

Eric W. Weisstein, Jun 28 2017

Keywords

• nonn
• more

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.

Crossrefs

Cf. A141243, A289203, A287071, A289200.

Programs

Mathematica

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

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+kChai Wah Wu, Jan 11 2024

Extensions

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