Abstract
Let \(k \ge 3\) be an integer and \(\Omega \) a set of size \(2k+1.\) We examine the binary codes generated by the row span of biadjacency matrices of the bipartite graphs \(\Gamma (2k+1,k,k+2,1).\) Adjacency in these graphs is defined by two vertices as k-subsets and \((k+2)\)-subsets of \(\Omega \) being adjacent if and only if they have one element in common. We show that \(S_{2k+1}\) is contained in the automorphism group of the graphs and the codes. In addition, we determine the duals of the codes, and by identifying suitable information sets, we construct 2-PD sets for the dual codes.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Fish, W., Key, J., Mwambene, E.: Codes from the incidence matrices of graphs on \(3\)-sets. Discrete Math. 311, 1823–1840 (2011)
Fish, W., Key, J., Mwambene, E.: Codes from incidence matrices and line graphs of Hamming graphs. Discrete Math. 310, 1884–1897 (2011)
Fish, W., Mumba, N.B., Mwambene, E., Rodrigues, B.G.: Binary codes and partial permutation decoding sets from biadjacency matrices of bipartite graphs \(\Gamma (2k,k,k+1,1).\) (Submitted)
Fish, W.: Codes from uniform subset graphs and cycle products, Ph.D. Thesis, University of the Western Cape (2007)
Fish, W., Fray, R., Mwambene, E.: Binary codes and partial permutation decoding sets from the odd graphs. Cent. Eur. J. Math. 12, 1362–1371 (2014)
Gordon, D.M.: Minimal permutation sets for decoding the binary Golay codes. IEEE Trans. Inform. Theory 28, 541–543 (1982)
Haemers, W.H., Peeters, R., van Rijckevorsel, J.M.: Binary codes of strongly regular graphs. Des. Codes Cryptogr. 17, 187–209 (1999)
Huffman, W.C.: Codes and groups. In: Pless, V.S., Huffman, W.C. (eds.) Handbook of Coding Theory, pp. 1345–1440. Elsevier, Amsterdam (1998)
Key, J.D., Moori, J., Rodrigues, B.G.: Permutation decoding sets for the binary codes from triangular graphs. Eur. J. Combin. 25, 113–123 (2004)
Key, J.D., Moori, J., Rodrigues, B.G.: Ternary codes from graphs on triples. Discrete Math. 309, 4663–4681 (2009)
Key, J.D., Moori, J., Rodrigues, B.G.: Codes associated with triangular graphs, and permutation decoding. Int. J. Inform. and Coding Theory 1, 334–349 (2010)
Kroll, H.J., Vincent, R.: PD-sets related to the codes of some classical varieties. Discrete Appl. Math. 301, 89–105 (2005)
MacWilliams, F.J.: Permuation decoding of systematic codes. Bell Syst. Tech. J. 43, 485–505 (1964)
Acknowledgements
N. Mumba acknowledges the postgraduate scholarship of AIMS (South Africa) and the support of the Department of Mathematics and Applied Mathematics, University of the Western Cape, South Africa. B. G. Rodrigues gratefully acknowledges support by the National Research Foundation of South Africa through Grant Numbers 87470 and 91495.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Fish, W., Mumba, N.B., Mwambene, E. et al. Binary Codes and Partial Permutation Decoding Sets from Biadjacency Matrices of the Bipartite Graphs \(\Gamma (2k+1,k,k+2,1)\) . Graphs and Combinatorics 33, 357–368 (2017). https://doi.org/10.1007/s00373-017-1765-8
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-017-1765-8