For Which Graphs Does Every Edge Belong to Exactly Two Chordless Cycles?

Abstract

A graph is 2-cycled if each edge is contained in exactly two of its chordless cycles. The 2-cycled graphs arise in connection with the study of balanced signing of graphs and matrices. The concept of balance of a $\{0,+1,-1\}$-matrix or a signed bipartite graph has been studied by Truemper and by Conforti et al. The concept of $\alpha$-balance is a generalization introduced by Truemper. Truemper exhibits a family ${\cal F}$ of planar graphs such that a graph $G$ can be signed to be $\alpha$-balanced if and only if each induced subgraph of $G$ in ${\cal F}$ can. We show here that the graphs in ${\cal F}$ are exactly the 2-connected 2-cycled graphs.