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

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

Offset

1,1

Comments

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

Links

Table of n, a(n) for n=1..9.

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

Cf. A291297, A291573.

Sequence in context: A032161 A265801 A098738 * A083701 A076996 A139148

Adjacent sequences: A291739 A291740 A291741 * A291743 A291744 A291745

Keyword

nonn,more

Author

Andrew Howroyd, Aug 30 2017

Extensions

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

Status

approved