A157887 The domatic number of the n-cube.

1, 2, 2, 4, 4, 4, 5, 8, 8, 8

Offset: 0

Author

Sune Kristian Jakobsen (sunejakobsen(AT)hotmail.com), Mar 08 2009

Keywords

• nonn
• hard
• more

Comments

It is known that a(n)=n+1 when n is of the form 2^k-1, and a(n)=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

Examples

			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.
		

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.
• Todd Trimble, Solution to POW-12: A graph coloring problem
• Eric Weisstein's World of Mathematics, Domatic Number
• Eric Weisstein's World of Mathematics, Hypercube Graph
• Wikipedia, Domatic number

Extensions

a(9) from Stan Wagon, Jul 15 2017