login
Number of maximal independent vertex sets in the n X n giraffe graph.
1

%I #25 Feb 07 2024 09:37:03

%S 1,1,1,1,90,3098,69369,3087085,29206276,4615678629,464716001925

%N Number of maximal independent vertex sets in the n X n giraffe graph.

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

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

%t Table[Length@FindIndependentVertexSet[RelationGraph[Sort[Abs[Subtract[##]]] == {1, 4} &, Tuples[Range[n], 2]], Infinity, All], {n, 7}]

%o (Python)

%o from networkx import empty_graph, complement, find_cliques

%o def A367458(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,4),(1,-4),(-1,4),(-1,-4),(4,1),(4,-1),(-4,1),(-4,-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 27 2024

%K nonn,more

%O 1,5

%A _Eric W. Weisstein_, Jan 26 2024