|
| |
|
|
A006946
|
|
Independence number of De Bruijn graph of order n on two symbols.
(Formerly M0834)
|
|
4
|
|
|
|
1, 2, 3, 7, 13, 28, 55, 114, 227, 466, 931, 1891, 3781
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
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
|
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
Table of n, a(n) for n=1..13.
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
|
|
|
MATHEMATICA
|
Length /@ Table[FindIndependentVertexSet[DeBruijnGraph[2, n]][[1]], {n, 6}]
|
|
|
PROG
|
(Python)
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.graph_clique_number(nx.complement(nx.Graph(deBruijn(n)))) # Pontus von Brömssen, Mar 07 2020
|
|
|
CROSSREFS
|
Cf. A000031, A333077, A333078.
Sequence in context: A088172 A048573 A221834 * A074129 A233042 A055003
Adjacent sequences: A006943 A006944 A006945 * A006947 A006948 A006949
|
|
|
KEYWORD
|
nonn,more,hard
|
|
|
AUTHOR
|
N. J. A. Sloane, Herb Taylor
|
|
|
EXTENSIONS
|
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
|
|
|
STATUS
|
approved
|
| |
|
|
