|
|
A157887
|
|
The domatic number of the n-cube.
|
|
1
|
|
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn,hard,more
|
|
AUTHOR
|
Sune Kristian Jakobsen (sunejakobsen(AT)hotmail.com), Mar 08 2009
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|