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

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

Offset

1,5

Links

Table of n, a(n) for n=1..11.

Eric Weisstein's World of Mathematics, Giraffe Graph.

Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set.

Mathematica

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

Prog

(Python)
from networkx import empty_graph, complement, find_cliques
def A367458(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, 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)
    return sum(1 for c in find_cliques(complement(G))) # Chai Wah Wu, Jan 27 2024

Crossrefs

Sequence in context: A013413 A013411 A013415 * A240426 A065950 A058830

Adjacent sequences: A367455 A367456 A367457 * A367459 A367460 A367461

Keyword

nonn,more

Author

Eric W. Weisstein, Jan 26 2024

Status

approved