A333077 -id:A333077 - cp's OEIS frontend

A006946 Independence number of de Bruijn graph of order n on two symbols.

1, 2, 3, 7, 13, 28, 55, 114, 227, 466, 931, 1891, 3781

Offset: 1

Proposition 4.3 (b) in Lichiardopol's paper (see links) can be formulated as a(n) <= 2^(n-1) - A000031(n)/2 + 1 for odd n. For even n, Proposition 5.4 says that a(n) <= (a(n+1) + 1)/2 <= 2^(n-1) - A000031(n+1)/4 + 1. For n<=13, equality holds in both cases, and I conjecture that it holds for all n. If this is true, the sequence would continue a(14)=7645, a(15)=15289, a(16)=30841, a(17)=61681, ... - Pontus von Brömssen, Feb 29 2020

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Pontus von Brömssen, Maximum independent sets for de Bruijn graphs of order 8 to 13
N. Lichiardopol, Independence number of de Bruijn graphs, Discrete Math., 306 (2006), no.12, 1145-1160. [Herman Jamke (hermanjamke(AT)fastmail.fm), Sep 07 2010]
Eric Weisstein's World of Mathematics, de Bruijn Graph
Eric Weisstein's World of Mathematics, Independence Number

Cf. A000031, A333077, A333078.

Length /@ Table[FindIndependentVertexSet[DeBruijnGraph[2, n]][[1]], {n, 6}]

import networkx as nx
def deBruijn(n):
    return nx.MultiDiGraph(((0, 0), (0, 0))) if n==0 else nx.line_graph(deBruijn(n-1))
def A006946(n):
    return nx.max_weight_clique(nx.complement(nx.Graph(deBruijn(n))),weight=None)[1] #Pontus von Brömssen, Mar 07 2020 (updated Nov 12 2023)

a(7) from Herman Jamke (hermanjamke(AT)fastmail.fm), Sep 07 2010

a(8) to a(13) from Pontus von Brömssen, Feb 29 2020

A333078 Number of maximum independent sets in the binary de Bruijn graph of order n.

Original entry on oeis.org

1, 2, 1, 6, 2, 44, 8

Offset: 0

Pontus von Brömssen, Mar 07 2020

Eric Weisstein's World of Mathematics, de Bruijn Graph
Eric Weisstein's World of Mathematics, Maximum Independent Vertex Set
Wikipedia, De Bruijn graph
Wikipedia, Independent set

Cf. A006946, A333077.

A359995 Number of maximal independent sets in the 2-Fibonacci digraph of order n.

Original entry on oeis.org

2, 3, 4, 10, 32, 184, 5110, 681454

Offset: 1

Pontus von Brömssen, Jan 21 2023

See Dalfó and Fiol (2019) or A360000 for the definition of the 2-Fibonacci graph.

The loop at node 0 is disregarded, so 0 is allowed in the independent sets.

C. Dalfó and M. A. Fiol, On d-Fibonacci digraphs, arXiv:1909.06766 [math.CO], 2019.

Cf. A333077, A359994, A359996, A360000.

import networkx as nx
def F(n): return nx.DiGraph(((0,0),(0,1),(1,0))) if n == 1 else nx.line_graph(F(n-1))
def A359995(n): return sum(1 for c in nx.find_cliques(nx.complement(nx.Graph(F(n)))))

cp's OEIS Frontend

A006946 Independence number of de Bruijn graph of order n on two symbols.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A333078 Number of maximum independent sets in the binary de Bruijn graph of order n.

Views

Author

Keywords

Links

Crossrefs

A359995 Number of maximal independent sets in the 2-Fibonacci digraph of order n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python