A Characterization of Graphs by Codes from their Incidence Matrices

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


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 \times \frac{1}{2}nk$ 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.


Codes; Graphs; Edge-connectivity

Full Text: PDF