tailieunhanh - Báo cáo toán học: " For which graphs does every edge belong to exactly two chordless cycles"

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 .