A367686 Number of maximal independent vertex sets and minimal vertex covers in the n-Pell graph.

2, 3, 17, 668, 5279875

Offset

1,1

Links

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

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

Eric Weisstein's World of Mathematics, Minimal Vertex Cover

Eric Weisstein's World of Mathematics, Pell Graph

Prog

(Python)
from itertools import product, combinations, groupby, islice
from networkx import empty_graph, find_cliques
def A367686(n):
    G = empty_graph(v for v in product((0, 1, 2), repeat=n) if not any(len(list(g))&1 and k==2 for k, g in groupby(v)))
    for a, b in combinations(G, 2):
        r = tuple(islice((i for i in range(n) if a[i]!=b[i]), 3))
        if len(r)==1:
            if a[r[0]]==2 or b[r[0]]==2:
                G.add_edge(a, b)
        elif len(r)==2:
            if not (r[0]+1==r[1] and a[r[0]] and b[r[0]] and a[r[0]]==a[r[1]] and b[r[0]]==b[r[1]]):
                G.add_edge(a, b)
        else:
            G.add_edge(a, b)
    return sum(1 for c in find_cliques(G)) # Chai Wah Wu, Jan 18 2024

Crossrefs

Sequence in context: A041383 A389935 A042903 * A394419 A132534 A263048

Adjacent sequences: A367683 A367684 A367685 * A367687 A367688 A367689

Keyword

nonn,more

Author

Eric W. Weisstein, Nov 26 2023

Status

approved