A291742 Number of maximal independent vertex sets in the n-Fibonacci cube graph.

2, 2, 3, 7, 22, 123, 2281, 221074, 300492228

Offset: 1

Author

Andrew Howroyd, Aug 30 2017

Keywords

• nonn
• more

Comments

The size of the smallest set, the independent domination number, is given by A291297.

Examples

			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.
		

Links

• Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
• Eric Weisstein's World of Mathematics, Fibonacci Cube Graph
• Wikipedia, Fibonacci cube

Crossrefs

Cf. A291297, A291573.

Programs

Python

from itertools import combinations, product
from networkx import empty_graph, find_cliques
def A291742(n):
    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

Extensions

a(9) from Pontus von Brömssen, Mar 06 2020