A289201 - OEIS

%I #19 Jan 12 2024 00:58:53

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

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

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/KnightGraph.html">Knight Graph</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximalIndependentVertexSet.html">Maximal Independent Vertex Set</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MinimalVertexCover.html">Minimal Vertex Cover</a>.

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

%o (Python)

%o from networkx import empty_graph, find_cliques, complement

%o def A289201(n):

%o     G = empty_graph((i,j) for i in range(n) for j in range(n))

%o     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)

%o     return sum(1 for c in find_cliques(complement(G))) # _Chai Wah Wu_, Jan 11 2024

%Y Cf. A141243, A289203, A287071, A289200.

%K nonn,more

%O 1,3

%A _Eric W. Weisstein_, Jun 28 2017

%E a(9)-a(10) from _Andrew Howroyd_, Jul 01 2017