×

For which graphs does every edge belong to exactly two chordless cycles? (English) Zbl 0851.05072

Electron. J. Comb. 3, No. 1, Research paper R14, 18 p. (1996); printed version J. Comb. 3, No. 1, 189-206 (1996).
Summary: 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 \({\mathcal 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 \({\mathcal F}\) can. We show here that the graphs in \({\mathcal F}\) are exactly the 2-connected 2-cycled graphs.

MSC:

05C38 Paths and cycles
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: EuDML EMIS