A characterization of graphs by codes from their incidence matrices (Q396825)

Summary: 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.