cp's OEIS Frontend

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

%I A006946 M0834 #59 Jun 03 2025 15:47:03
%S A006946 1,2,3,7,13,28,55,114,227,466,931,1891,3781
%N A006946 Independence number of de Bruijn graph of order n on two symbols.
%C A006946 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
%D A006946 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006946 Pontus von Brömssen, <a href="/A006946/a006946.txt">Maximum independent sets for de Bruijn graphs of order 8 to 13</a>
%H A006946 N. Lichiardopol, <a href="http://dx.doi.org/10.1016/j.disc.2005.10.032">Independence number of de Bruijn graphs</a>, Discrete Math., 306 (2006), no.12, 1145-1160. [Herman Jamke (hermanjamke(AT)fastmail.fm), Sep 07 2010]
%H A006946 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/deBruijnGraph.html">de Bruijn Graph</a>
%H A006946 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IndependenceNumber.html">Independence Number</a>
%t A006946 Length /@ Table[FindIndependentVertexSet[DeBruijnGraph[2, n]][[1]], {n, 6}]
%o A006946 (Python)
%o A006946 import networkx as nx
%o A006946 def deBruijn(n):
%o A006946     return nx.MultiDiGraph(((0, 0), (0, 0))) if n==0 else nx.line_graph(deBruijn(n-1))
%o A006946 def A006946(n):
%o A006946     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)
%Y A006946 Cf. A000031, A333077, A333078.
%K A006946 nonn,more,hard
%O A006946 1,2
%A A006946 _N. J. A. Sloane_, Herb Taylor
%E A006946 a(7) from Herman Jamke (hermanjamke(AT)fastmail.fm), Sep 07 2010
%E A006946 a(8) to a(13) from _Pontus von Brömssen_, Feb 29 2020