[Jump to code hierarchy]

Graph-adjacency code[1,2]

Description

Binary linear code whose generator matrix is that of the row space of the adjacency matrix of a strongly regular graph. Given an adjacency matrix \(A\), the generator matrix is either \(G=A\) or \(G=(I|A)\), where \(I\) is the identity matrix.

Codes based on strongly regular graphs are sometimes optimal or nearly optimal for their length and size [1].

Cousins

  • Cycle code— Graph-adjacency (cycle) codes’ generator (parity-check) matrices are defined using adjacency (incidence) matrices of graphs.
  • Hermitian qubit code— Bounds on self-dual \([[n,0,d]]\) Hermitian codes based on graphs have been derived [2].

Member of code lists

Primary Hierarchy

Classical Domain
Binary Kingdom
Binary codeECC
Binary group-orbit codeECC
Linear binary codeLinear \(q\)-ary Linear code over \(\mathbb{Z}_q\) ECC
Parents
Linear binary code
Graph-adjacency code
Children
Higman-Sims graph-adjacency code
Hoffman-Singleton graph-adjacency code

References

[1]
V. D. Tonchev, “Binary codes derived from the Hoffman-Singleton and Higman-Sims graphs”, IEEE Transactions on Information Theory 43, 1021 (1997) DOI
[2]
V. D. Tonchev, “Error-correcting codes from graphs”, Discrete Mathematics 257, 549 (2002) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

— see instructions

Zoo Code ID: graph

Cite as:
“Graph-adjacency code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/graph, arXiv:2606.11484
BibTeX:
@incollection{eczoo_graph,
title={Graph-adjacency code},
booktitle={The Error Correction Zoo},
year={2026},
editor={Albert, Victor V. and Faist, Philippe},
eprint={2606.11484},
doi={10.48550/arXiv.2606.11484},
url={https://errorcorrectionzoo.org/c/graph}
}
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/graph

Cite as:

“Graph-adjacency code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/graph, arXiv:2606.11484

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/graph/adjacency/graph.yml.