Open Access
A
Binary codes from graphs related to the Johnson graph Γ(n, k, k − 1)
W. Fishwfish@uwc.ac.zaDepartment of Mathematics and Applied MathematicsPrivate Bag X17, Bellville 7535University of the Western CapeSouth AfricaView full profile → , *N. B. MumbaCorresponding authornephtale@aims.ac.zaDepartment of Mathematics and StatisticsPrivate Bag 201, MzuzuMzuzu UniversityMalawiView full profile →
* Corresponding author · click or hover a name for details
- Received:
- 01 Dec 2020
- Accepted:
- 05 May 2021
- Published Online:
- 08 Mar 2022
- Article type:
- A
- Language:
- EN
- Article no.:
- JDMSC-1410
- Pages:
- 443–457
Abstract
We show that the binary codes generated by the row span of adjacency matrices of the uniform subset graph Γ(2k, k, 1) and the Johnson graph Γ(2k, k, k − 1) coincide despite the graphs being non-isomorphic. We extend our results to the binary codes of Γ(2k, k, i) and k Γ(2k, k, k − i) where (k even), by showing that their adjacency matrices are equivalent. Further, we discuss the binary codes from the generalised uniform subset graph Γ(2k, k, I) for I = {1, k − 1}, and show that they are self-orthogonal for k ≥ 3.
Keywords
Subject Classifications
94B0505B3005C9005E20
References
- W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I: The user language, J. Symbolic Comput., 24 (1997), 235-265. doi: https://doi.org/10.1006/jsco.1996.0125 [Crossref], [Web of Science ®], [Google Scholar]
- A. E. Brouwer and J. H. van Eijl, On the p-rank of the adjacency matrices of strongly regular graphs, J. Algebraic Combin., 1 (1992), 329-346. doi: https://doi.org/10.1023/A:1022438616684 [Crossref], [Google Scholar]
- Y. Chen and Y. Wang, On the diameter of generalised Kneser graphs, Discrete Math., 308 (2008), 4276-4279. doi: https://doi.org/10.1016/j.disc.2007.08.004 [Crossref], [Web of Science ®], [Google Scholar]
- Y. Chen and W. Wang, Diameters of uniform subset graphs, Discrete Math., 308 (2008), 6645-6649. doi: https://doi.org/10.1016/j.disc.2007.11.031 [Crossref], [Web of Science ®], [Google Scholar]
- B-L Chen and K-W Lih, Hamiltonian uniform subset graphs, J. Combin. Theory Ser. B, 42 (1987), 257-263. doi: https://doi.org/10.1016/0095-8956(87)90044-X [Crossref], [Web of Science ®], [Google Scholar]
- P. Dankelman, J. D. Key and B. G. Rodrigues, A characterisation of graphs by codes from their incidence matrices, Electron. J. Combin., 20 (3) (2013), # P18. doi: https://doi.org/10.37236/2770 [Crossref], [Web of Science ®], [Google Scholar]
- P. Dankelman, J. D. Key and B. G. Rodrigues, Codes from incidence matrices of graphs, Des. Codes Cryptogr., 68 (2013), 373-393. doi: https://doi.org/10.1007/s10623-011-9594-x [Crossref], [Web of Science ®], [Google Scholar]
- W. Fish, Codes from uniform subset graphs and cycle products, Ph.D. Thesis, University of the Western Cape, 2007. [Google Scholar]
- W. Fish, Binary Codes and Partial Permutation Decoding Sets from the Johnson Graphs, Graphs Combin., 31 (2015), 1381-1396. doi: https://doi.org/10.1007/s00373-014-1485-2 [Crossref], [Web of Science ®], [Google Scholar]
- W. Fish, R. Fray and E. Mwambene, Binary codes and partial permutation decoding sets from the odd graphs, Cent. Eur. J. Math., 12 (2014), 1362-1371. [Web of Science ®], [Google Scholar]
- W. Fish, J. D. Key and E. Mwambene, Binary codes of line graphs from the n -cube. J. Symbolic Comput., 45 (2010) 800-812. doi: https://doi.org/10.1016/j.jsc.2010.03.012 [Crossref], [Web of Science ®], [Google Scholar]
- W. Fish, J. D. Key and E. Mwambene, Codes from the incidence matrices of graphs on 3 -sets, Discrete Math., 311 (2011), 1823-1840. doi: https://doi.org/10.1016/j.disc.2011.04.029 [Crossref], [Web of Science ®], [Google Scholar]
- W. Fish, J. D. Key and E. Mwambene, Codes from incidence matrices and line graphs of Hamming graphs, Discrete Math., 310 (2010), 1884–1897. doi: https://doi.org/10.1016/j.disc.2010.02.010 [Crossref], [Web of Science ®],
Views: 271Downloads: 70Citations: 0
