A Characterization of Graphs by Codes from their Incidence Matrices

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

##article.abstract##


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.


##article.subject##


Codes; Graphs; Edge-connectivity

Full Text: PDF