A029866 -id:A029866 - cp's OEIS frontend

A000983 Size of minimal binary covering code of length n and covering radius 1.

1, 2, 2, 4, 7, 12, 16, 32, 62

Offset: 1

For k > 0, a(2^k-1) = 2^(2^k-k-1). In this case the minimal covering code is also a Hamming code.
In the game described in the Wikipedia link, with n players, the optimal strategy wins with probability 1-a(n)/2^n. In the optimal strategy, the players first agree on a minimal covering code of length n. After the hats are placed, each player knows two words of length n such that one of them is the hat colors of the n players. If one of these two words is a member of the covering code and the other word is not, that player guesses the word that is not. Otherwise, that player does not guess. This strategy guarantees that the team wins for all words that are not members of the covering code.
Because each codeword covers n+1 of the 2^n words, A053637(n+1) is a lower bound. - Rob Pratt, Jan 05 2015
a(n) is also the domination number of the n-hypercube graph Q_n. - Eric W. Weisstein, Feb 20 2016
The next term a(10) is in the range 107-120. - Andrey Zabolotskiy, Sep 01 2016

G. D. Cohen et al., Covering Codes, North-Holland, 1997, p. 166.
I. S. Honkala and Patric R. J. Östergård, Code design, Chapter 13 of Local Search in Combinatorial Optimization, E. Aarts and J. K. Lenstra (editors), Wiley, New York 1997, pp. 441-456.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Jernej Azarija, M. A. Henning, S. Klavzar, (Total) Domination in Prisms, arXiv preprint arXiv:1606.08143 [math.CO], 2016. See Table 1.
R. Bertolo, Patric R. J. Östergård and W. D. Weakley, An updated table of binary/ternary mixed covering codes, J. Combin. Designs, 12 (2004), 157-176, DOI:10.1002/jcd.20008. [a(10)>=107]
H. Hamalainen et al., Football pools - a game for mathematicians, Amer. Math. Monthly, 102 (1995), 579-588.
J. G. Kalbfleisch and R. G. Stanton, A combinatorial problem in matching, J. London Math. Soc., 44 (1969), 60-64.
Dmitry Kamenetsky, Best known solutions for n <= 11.
A. Lobstein, G. Cohen and N. J. A. Sloane, Recouvrements d'Espaces de Hamming Binaires, C. R. Acad. Sci. Paris, Series I, 301 (1985), 135-138.
Patric R. J. Östergård and Markku K. Kaikkonen, New upper bounds for binary covering codes, Discrete Mathematics 178 (1998), 165-179.
Patric R. J. Östergård and U. Blass, On the size of optimal binary codes of length 9 and covering radius 1, IEEE Trans. Inform. Theory, 47 (2001), 2556-2557. [Determines a(9)].
Eric Weisstein's World of Mathematics, Domination Number
Eric Weisstein's World of Mathematics, Hypercube Graph
Wikipedia, Hat puzzle (Ebert's version and Hamming codes)
Index entries for sequences related to covering codes

A column of A060438. Cf. A029866.

A060438 Triangle T(n,k), 1 <= k <= n, giving maximal size of binary code of length n and covering radius k.

Original entry on oeis.org

1, 2, 1, 2, 2, 1, 4, 2, 2, 1, 7, 2, 2, 2, 1, 12, 4, 2, 2, 2, 1, 16, 7, 2, 2, 2, 2, 1, 32, 12, 4, 2, 2, 2, 2, 1, 62, 16, 7, 2, 2, 2, 2, 2, 1

Offset: 1

N. J. A. Sloane, Apr 07 2001

			Triangle starts:
1;
2,1;
2,2,1;
4,2,2,1;
7,2,2,2,1;
...

G. D. Cohen et al., Covering Codes, North-Holland, 1997, p. 166.

W. Haas, Binary and ternary codes of covering radius one: some new lower bounds, Discrete Math., 245 (2002), 161-178.
Gerzson Kéri, Tables for Bounds on Covering Codes.
Index entries for sequences related to covering codes

Columns give A000983, A029866. Cf. A060439, A060440.

Row 9 from Andrey Zabolotskiy, Apr 11 2017 using Gerzson Kéri's tables.

A290128 Domatic number of the halved n-cube graph.

Original entry on oeis.org

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

Offset: 1

Stan Wagon, Jul 20 2017

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.

			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.

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

A157887 has the domatic number for Hamming radius 1.

A029866 has the domination number for these graphs.

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

cp's OEIS Frontend

A000983 Size of minimal binary covering code of length n and covering radius 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A060438 Triangle T(n,k), 1 <= k <= n, giving maximal size of binary code of length n and covering radius k.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Extensions

A290128 Domatic number of the halved n-cube graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions