Codes from incidence matrices of graphs

P. Dankelmann, J. D. Key, B. G. Rodrigues

Research output: Contribution to journalArticlepeer-review

28 Citations (Scopus)


We examine the p-ary codes, for any prime p, from the row span over ∥V × ∥E incidence matrices of connected graphs Γ = (V, E), showing that certain properties of the codes can be directly derived from the parameters and properties of the graphs. Using the edge-connectivity of Γ (defined as the minimum number of edges whose removal renders Γ disconnected) we show that, subject to various conditions, the codes from such matrices for a wide range of classes of connected graphs have the property of having dimension |V| or |V| - 1, minimum weight the minimum degree δ(Γ), and the minimum words the scalar multiples of the rows of the incidence matrix of this weight. We also show that, in the k-regular case, there is a gap in the weight enumerator between k and 2k - 2 of the binary code, and also for the p-ary code, for any prime p, if Γ is bipartite. We examine also the implications for the binary codes from adjacency matrices of line graphs. Finally we show that the codes of many of these classes of graphs can be used for permutation decoding for full error correction with any information set.

Original languageEnglish
Pages (from-to)373-393
Number of pages21
JournalDesigns, Codes, and Cryptography
Issue number1-3
Publication statusPublished - Jul 2013


  • Codes
  • Graphs
  • Incidence matrices
  • Permutation decoding

ASJC Scopus subject areas

  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'Codes from incidence matrices of graphs'. Together they form a unique fingerprint.

Cite this