tailieunhanh - Báo cáo toán học: "Ear decompositions in combed graphs"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Ear decompositions in combed graphs. | Ear decompositions in combed graphs Marcelo H. de Carvalhoy Federal University of Mato Grosso do Sul Campo Grande Brazil C. H. C. Littlez Massey University Palmerston North New Zealand Submitted Nov 8 2006 Accepted Jan 18 2008 Published Jan 28 2008 Mathematics Subject Classification 05C70 Abstract We introduce the concept of combed graphs and present an ear decomposition theorem for this class of graphs. This theorem includes the well known ear decomposition theorem for matching covered graphs proved by Lovasz and Plummer. Then we use the ear decomposition theorem to show that any two edges of a 2-connected combed graph lie in a balanced circuit of an equivalent combed graph. This result generalises the theorem that any two edges in a matching covered graph with at least four vertices belong to an alternating circuit. 1 Introduction Let G be a graph and T a subset of EG. We view circuits as sets of edges. A circuit C in G is T-conservative if at most half its edges are in T. We say that T is conservative if every circuit in G is T-conservative. In this case we also say that G is conservative with respect to T. Now let G be a bipartite graph with bipartition A B . We have written A B rather than A Bg to emphasise that we are imposing an ordering on the members of the bipartition. Let T be a subset of EG. A circuit C is T-balanced or balanced with respect to T if each vertex of C in B is incident with a unique edge of T C. We say that T is balanced if every edge of G lies in a T -balanced circuit. In this case we refer to G as a T -balanced graph. Supported by ProNEx - FAPESP cNPq CNPq and FUNDECT-MS Brazil. ySupported by CNPq Brazil. zWork done during this author s visit to UFMS Brazil in 2006. The author thanks CNPq for its support. THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R19 1 We describe T as a comb if it is balanced and conservative. We also refer to G as combed by T. Combs generalise the basic combs of Padayachee 5 where each vertex of B is incident .