login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Number of maximum independent vertex sets in the n X n antelope graph.
1

%I #12 Feb 12 2024 13:30:04

%S 1,1,1,1,1,1,8,4,4,4,4,4,1,2,290

%N Number of maximum independent vertex sets in the n X n antelope graph.

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

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

%t Table[Length@With[{g = RelationGraph[Sort[Abs[Subtract[##]]] == {3, 4} &, Tuples[Range[n], {2}]]}, FindIndependentVertexSet[g, Length /@ FindIndependentVertexSet[g], All]], {n, 8}]

%o (Python)

%o from collections import Counter

%o from networkx import empty_graph, find_cliques, complement

%o def A370198(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 ((3,4),(3,-4),(-3,4),(-3,-4),(4,3),(4,-3),(-4,3),(-4,-3)) if 0<=i+k<n and 0<=j+l<n)

%o return (x:=Counter(len(c) for c in find_cliques(complement(G))))[max(x)] # _Chai Wah Wu_, Feb 12 2024

%K nonn,more,hard

%O 1,7

%A _Eric W. Weisstein_, Feb 11 2024