Generalized hypercube graph $\Q_n(S)$, graph products and self-orthogonal codes

Abstract

A generalized hypercube graph $\Q_n(S)$ has $\F_{2}^{n}=\{0,1\}^n$ as the vertex set and two vertices being adjacent whenever their mutual Hamming distance belongs to $S$, where $n \ge 1$ and $S\subseteq \{1,2,\ldots, n\}$. The graph $\Q_n(\{1\})$ is the $n$-cube, usually denoted by $\Q_n$. We study graph boolean products $G_1 = \Q_n(S)\times \Q_1, G_2 = \Q_{n}(S)\wedge \Q_1$, $G_3 = \Q_{n}(S)[\Q_1]$ and show that binary codes from neighborhood designs of $G_1, G_2$ and $G_3$ are self-orthogonal for all choices of $n$ and $S$. More over, we show that the class of codes $C_1$ are self-dual. Further we find subgroups of the automorphism group of these graphs and use these subgroups to obtain PD-sets for permutation decoding. As an example we find a full error-correcting PD set for the binary $[32, 16, 8]$ extremal self-dual code.

Keywords

• Graphs, Designs, Codes, Permutation decoding

References

1. A. Berrachedi, M. Mollard, On two problems about (0, 2)-graphs and interval-regular graphs, Ars
2. Combin. 49 (1998) 303–309.
3. W. Fish, J. D. Key, E. Mwambene, Graphs, designs and codes related to the n-cube, Discrete Math. 309(10) (2009) 3255–3269.
4. F. Harary, G. W. Wilcox, Boolean operations on graphs, Math. Scand. 20 (1967) 41–51.
5. W. C. Huffman. Codes and groups. In V. Pless and W. C. Huffman, Eds., Handbook of coding theory, Vol. 2, pp. 1345–1440, Elsevier Science Publishers, Amsterdam, The Netherlands, 1998.
6. J. D. Key, P. Seneviratne, Permutation decoding for binary self-dual codes from the graph Qn, where n is even. In T. Shaska, W. C. Huffman, D. Joyner, and V. Ustimenko, Eds., Advances in Coding Theory and Cryptography, Series on Coding Theory and Cryptography, Vol. 3, pp. 152–159, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2007.
7. J. M. Laborde, R. M. Madani, Generalized hypercubes and (0, 2)-graphs, Discrete Math. 165/166 (1997) 447–459.
8. F. J. MacWilliams, N. J. A. Sloane, The theory of error-correcting codes, Amsterdam: North-Holland, 1998.

9. M. Mulder, (0, λ)-graphs and n-cubes, Discrete Math. 28(2) (1979) 179–188.