A290128 Domatic number of the halved n-cube graph.

1, 2, 4, 4, 8, 16, 16, 18

Offset: 1

Author

Stan Wagon, Jul 20 2017

Keywords

• nonn
• hard
• more

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.

Examples

			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.
		

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

Crossrefs

A157887 has the domatic number for Hamming radius 1.

A029866 has the domination number for these graphs.

Extensions

a(8) = 18 from Rob Pratt and Stan Wagon, Jul 26 2017