A291742 Number of maximal independent vertex sets in the n-Fibonacci cube graph.
2, 2, 3, 7, 22, 123, 2281, 221074, 300492228
Offset: 1
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
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
Comments