login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A291742 Number of maximal independent vertex sets in the n-Fibonacci cube graph. 4
2, 2, 3, 7, 22, 123, 2281, 221074, 300492228 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,1
COMMENTS
The size of the smallest set, the independent domination number, is given by A291297.
LINKS
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
Eric Weisstein's World of Mathematics, Fibonacci Cube Graph
Wikipedia, Fibonacci cube
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
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
CROSSREFS
Sequence in context: A032161 A265801 A098738 * A083701 A076996 A139148
KEYWORD
nonn,more
AUTHOR
Andrew Howroyd, Aug 30 2017
EXTENSIONS
a(9) from Pontus von Brömssen, Mar 06 2020
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 16:58 EDT 2024. Contains 371254 sequences. (Running on oeis4.)