A333077 Number of maximal independent sets in the binary de Bruijn graph of order n.

1, 2, 3, 8, 64, 2626, 4850838

Offset: 0

Author

Pontus von Brömssen, Mar 07 2020

Keywords

• nonn
• hard
• more

Links

• Eric Weisstein's World of Mathematics, de Bruijn Graph
• Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
• Wikipedia, De Bruijn graph
• Wikipedia, Maximal independent set

Crossrefs

Cf. A006946, A333078.

Programs

Python

import networkx as nx
def deBruijn(n):
    return nx.MultiDiGraph(((0, 0), (0, 0))) if n==0 else nx.line_graph(deBruijn(n-1))
def A333077(n):
    return sum(1 for _ in nx.find_cliques(nx.complement(nx.Graph(deBruijn(n)))))
# replacement of a function removed from NetworkX by Ross Barnowski, Nov 12 2023