Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: Optimal Ear Decompositions Of Matching Covered Graphs And Bases For The Matching Lattice
Author: De Carvalho M.H.
Lucchesi C.L.
Murty U.S.R.
Abstract: This is a sequel to our papers (M. H. de Carvalho, C. L. Lucchesi, and U. S. R. Murty, 1999, Combinatorica 19, 151-174; 2002, J. Combin. Theory Ser. B 85, 94-136; and 2002, J. Combin. Theory Ser. B 85, 137-180). A Petersen brick is a graph whose underlying simple graph is isomorphic to the Petersen graph. For a matching covered graph G, b(G) denotes the number of bricks of G, and p(G) denotes the number of Petersen bricks of G. An ear decomposition of G is optimal if, among all ear decompositions of G, it uses the least possible number of double ears. Here we make use of the main theorem in (2002, J. Combin. Theory Ser. B 85, 137-180) to prove that the number of double ears in an optimal ear decomposition of a matching covered graph G is b(G) + p(G). In particular, if G is a brick that is not a Petersen brick, then there is an ear decomposition of G with exactly one double ear. This answers a question raised by D. Naddef and W. R. Pulleyblank (1982, Ann. Discrete Math. 16, 241-260). Using this theorem, we give an alternative proof of L. Lovász' matching lattice characterization theorem (1987, J. Combin. Theory Ser. B 43, 187-222). We also show that for any matching covered graph G, there is a basis for the matching lattice of G consisting of incidence vectors of perfect matchings of G. This answers a question raised by U. S. R. Murty (1994, "The Matching Lattice and Related Topics," Technical Report, University of Waterloo). In fact, we show that such a basis may be obtained from the incidence vectors of perfect matchings associated with optimal ear decompositions of G. © 2002 Elsevier Science (USA).
Rights: fechado
Identifier DOI: 10.1006/jctb.2001.2090
Date Issue: 2002
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
2-s2.0-0036266944.pdf216.65 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.