Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: For which graphs does every edge belong to exactly two chordless cycles? | For which graphs does every edge belong to exactly two chordless cycles Uri N. Peled1 and Julin Wu2 Dept. of Mathematics Statistics and Computer Science M C 249 The University of Illinois at Chicago 851 S. Morgan Street Chicago IL 60607-7045 Submitted December 2 1995 Accepted April 15 1996. Key Words Chordless cycles balanced graphs balanced matrices Mathematical Reviews Subject Numbers Primary 05C75 Secondary 05C3B 05C50 90C35 1 uripeled@uic .edu 2jwu2@ 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 a-balance is a generalization introduced by Truemper. Truemper exhibits a family F of planar graphs such that a graph G can be signed to be a-balanced if and only if each induced subgraph of G in F can. We show here that the graphs in F are exactly the 2-connected 2-cycled graphs. 1 Introduction A graph is said to be 2-cycled if each of its edges is contained in exactly two chordless cycles. The 2-cycled graphs arise in connection with the study of balanced signing of graphs and matrices by Truemper 3 and by Conforti et al. 2 as indicated in the next three paragraphs. A signed graph is a graph G V E together with a mapping f E 1 1 . Consider a mapping a C 0 1 2 3 where C is the set of chordless cycles of G. If e2Cf e a C mod 4 for all C 2 C we say that the signed graph is a-balanced. A trivial necessary condition which we assume throughout is that CI a C mod 2 for all C 2 C. When a 0 this condition means that G is bipartite in which case it can be specified by its adjacency matrix A and A is balanced in the usual sense if and only if the signed graph consisting of G and the constant mapping f 1 is 0-balanced. Similarly a 0 1 1 -matrix A specifies a signed bipartite graph and A is .