Maximality of the cycle code of a graph (Q1322205)

The cycle code (usually called cycle space) of a graph \(\Gamma\) is the linear span over GF(2) of the characteristic vectors of circuits versus edges. The authors investigate maximal cycle codes, in the sense that adding new code words will reduce the minimum distance. They characterize the graphs whose cycle codes are maximal. They show that such graphs have girth \(g\geq {1\over 2}(n-c)+ 1\), where \(n\) and \(c\) are the number of vertices and connected components.