login
A157887
The domatic number of the n-cube.
1
1, 2, 2, 4, 4, 4, 5, 8, 8, 8
OFFSET
0,2
COMMENTS
It is known that a(n)=n+1 when n is of the form 2^k-1, and a(n)<n+1 otherwise, a(n) is weakly increasing, and a(nm-1)>=a(n-1)a(m-1).
Patric R. J. Östergård proved that a_n/n->1 as n-> infinity. [From Sune Kristian Jakobsen (sunejakobsen(AT)hotmail.com), Mar 16 2009]
The value of A000983(9) = 62 means that any dominating set in G=HypercubeGraph[9] has size 62 or more. 9*62 > 512 so there cannot be 9 disjoint dominating sets in G. That there exist 8 disjoint dominating sets for G follows from the existence of 8 such sets for HypercubeGraph[8]: simply take any element in such a set and append both a 0 and 1 to it to turn it into a dominating set in dimension 9. The comment at A000983 about the dominating number for 10 being between 107 and 120 means that the domatic number here for n = 10 is either 8 or 9. - Stan Wagon, Jul 15 2017
LINKS
Patric R. J. Östergård, A Coloring Problem in Hamming Spaces, European Journal of Combinatorics, Volume 18, Number 3, April 1997, pp. 303-309.
Eric Weisstein's World of Mathematics, Domatic Number
Eric Weisstein's World of Mathematics, Hypercube Graph
Wikipedia, Domatic number
EXAMPLE
a(3)=4: The vertices of the 3-dimensional cube can be partitioned into 4 dominating sets, {000,111}, {001,110}, {010,101}, {011,100}, but not into 5. A subset of a graph is called dominating if every vertex in the graph is in the set or is a neighbor of a vertex in the set.
CROSSREFS
Sequence in context: A115367 A084841 A144202 * A292264 A265263 A113320
KEYWORD
nonn,hard,more
AUTHOR
Sune Kristian Jakobsen (sunejakobsen(AT)hotmail.com), Mar 08 2009
EXTENSIONS
a(9) from Stan Wagon, Jul 15 2017
STATUS
approved