Error-correcting codes from graphs Original Research Article

The paper surveys some constructions of linear binary codes defined by the adjacency matrices of undirected graphs. It is shown that the class of all graphs with n vertices leads to codes that for large n meet the Gilbert–Varshamov bound. Some interesting codes are obtainable from graphs with high degree of symmetry, such as strongly regular graphs. A relation between the linear binary codes derived from graphs and a class of quantum error-correcting codes is also discussed.