|
|
A291742
|
|
Number of maximal independent vertex sets in the n-Fibonacci cube graph.
|
|
4
|
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
The size of the smallest set, the independent domination number, is given by A291297.
|
|
LINKS
|
|
|
EXAMPLE
|
Case n=1: The vertices are 0, 1. Each singleton vertex set is a maximal independent set, so a(1) = 2.
Case n=2: The vertices are 00, 01, 10. Maximal independent sets are {00} and {01, 10}, so a(2) = 2.
Case n=3: The vertices are 000, 001, 010, 100, 101. Maximal independent sets are {000, 101}, {010, 101}, {001, 010, 100}, so a(3)=3.
|
|
PROG
|
(Python)
from itertools import combinations, product
from networkx import empty_graph, find_cliques
v = tuple(int(q, 2) for q in (''.join(p) for p in product('01', repeat=n)) if '11' not in q)
G = empty_graph(v)
e = tuple((a, b) for a, b in combinations(v, 2) if (lambda m: (m&-m)^m if m else 1)(a^b))
G.add_edges_from(e)
return sum(1 for c in find_cliques(G)) # Chai Wah Wu, Jan 14 2024
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|