OFFSET
1,2
COMMENTS
This is the same as the domatic number of the next lower Hamming radius 2 graph. See the Wikipedia link.
a(9) <= 21 because the domination number = 12 and floor(256/12) = 21.
a(10) is known to be 32 as the domination number is 16 and 512/16 is 32; this code is realized by a linear code in the Graham and Sloane paper.
LINKS
R. L. Graham and N. J. A. Sloane, On the Covering Radius of Codes, IEEE Trans. Inform. Theory, IT-31 (1985), 385-401.
Stan Wagon, Domatic data for halved cube graph
Eric Weisstein's World of Mathematics, Domatic Number
Eric Weisstein's World of Mathematics, Halved Cube Graph
Wikipedia, Halved cube graph
EXAMPLE
For n=3, two disjoint dominating sets for the Hamming radius-2 graph are {00, 11} and {10 01}, and this means a(2) = 2.
For n = 8, a(8) is the same as the domatic number of the Hamming radius 2 graph built from bit-strings of length 7.
A collection of 18 disjoint dominating sets showing a(8)=18 is:
{0, 18, 47, 57, 84, 107, 111}, {1, 58, 60, 71, 79, 118, 120},
{2, 31, 35, 42, 77, 89, 116}, {3, 7, 11, 12, 112, 125, 126},
{4, 20, 43, 68, 91, 117, 122}, {5, 39, 56, 67, 90, 94, 101},
{6, 53, 55, 73, 88, 98, 108, 123}, {8, 32, 63, 65, 86, 87, 104},
{9, 14, 30, 49, 81, 102, 121}, {10, 24, 40, 50, 69, 119, 127},
{13, 23, 37, 61, 80, 82, 106}, {15, 25, 26, 36, 92, 96, 100, 115},
{16, 21, 52, 59, 78, 99, 105}, {17, 19, 34, 76, 95, 109, 124},
{22, 29, 54, 62, 72, 75, 97}, {27, 38, 44, 64, 85, 110, 113},
{28, 41, 45, 66, 83, 103, 114}, {33, 46, 48, 51, 70, 74, 93},
where the integers from 0 to 127 encode the bit-strings.
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Stan Wagon, Jul 20 2017
EXTENSIONS
a(8) = 18 from Rob Pratt and Stan Wagon, Jul 26 2017
STATUS
approved