A290607 Number of maximal independent vertex sets (and minimal vertex covers) in the n-Keller graph.

1, 56, 1712, 46336, 1570048, 76425216

Offset: 1

Author

Eric W. Weisstein, Aug 07 2017

Keywords

• nonn
• more

Links

• Eric Weisstein's World of Mathematics, Keller Graph
• Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
• Eric Weisstein's World of Mathematics, Minimal Vertex Cover

Crossrefs

Cf. A258935, A284854.

Programs

Python

from itertools import zip_longest
from sympy.ntheory.factor_ import digits
from networkx import empty_graph, find_cliques
def A290607(n):
    k = 1<<(n<<1)
    G = empty_graph(range(k))
    G.add_edges_from((a,b) for a in range(k) for b in range(a) if (s:=tuple(c-d&3 for c, d in zip_longest(digits(a,4)[-1:0:-1],digits(b,4)[-1:0:-1],fillvalue=0))).count(2)==0 or s.count(0)>len(s)-2)
    return sum(1 for c in find_cliques(G)) # Chai Wah Wu, Jan 11 2024

Extensions

a(5) from Eric W. Weisstein, Nov 05 2018

a(6) from Chai Wah Wu, Jan 11 2024