|
%I #22 Feb 02 2020 22:24:16
%S 1,2,2,4,4,4,5,8,8,8
%N The domatic number of the n-cube.
%C 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).
%C 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]
%C 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
%H Patric R. J. Östergård, <a href="https://doi.org/10.1006/eujc.1996.0093">A Coloring Problem in Hamming Spaces</a>, European Journal of Combinatorics, Volume 18, Number 3, April 1997, pp. 303-309.
%H Todd Trimble, <a href="http://topologicalmusings.wordpress.com/2009/01/04/solution-to-pow-12-a-graph-coloring-problem">Solution to POW-12: A graph coloring problem</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DomaticNumber.html">Domatic Number</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HypercubeGraph.html">Hypercube Graph</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Domatic_number">Domatic number</a>
%e 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.
%K nonn,hard,more
%O 0,2
%A Sune Kristian Jakobsen (sunejakobsen(AT)hotmail.com), Mar 08 2009
%E a(9) from _Stan Wagon_, Jul 15 2017
|
