A characterization of graphs by codes from their incidence matrices

Peter Dankelmann, Jennifer D. Key, Bernardo G. Rodrigues

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)


We continue our earlier investigation of properties of linear codes generated by the rows of incidence matrices of k-regular connected graphs on n vertices. The notion of edge connectivity is used to show that, for a wide range of such graphs, the p-ary code, for all primes p, from an n × 1/2nk incidence matrix has dimension n or n - 1, minimum weight k, the minimum words are the scalar multiples of the rows, there is a gap in the weight enumerator between k and 2k - 2, and the words of weight 2k - 2 are the scalar multiples of the differences of intersecting rows of the matrix. For such graphs, the graph can thus be retrieved from the code.

Original languageEnglish
Article numberP18
JournalElectronic Journal of Combinatorics
Issue number3
Publication statusPublished - 16 Aug 2013


  • Codes
  • Edge-connectivity
  • Graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'A characterization of graphs by codes from their incidence matrices'. Together they form a unique fingerprint.

Cite this