A CODING APPROACH TO SIGNED GRAPHS

The cocycle code of an undirected graph Gamma is the linear span over F-2 of the characteristic vectors of cutsets. (If Gamma is complete bi partite, this is the generalized Gale-Berlekamp code.) The natural bij ection between the cosets of this code and the switching classes of si gned graphs based on Gamma is used to show that the number of such cla sses is equal to the number of even-degree subgraphs of Gamma in both the labeled and unlabeled cases and to improve by coding theory previo us bounds on D(Gamma), the maximum line index of imbalance of signings of Gamma. Bounds on D(Gamma) are obtained in terms of the genus of Ga mma and on the number of unlabeled even-degree subgraphs in terms of D (Gamma). Numerous examples are treated, including the ''grid'' (or ''l attice'') graphs that are of interest in the Ising model of spin glass es.