Optimal Ear Decompositions of Matching Covered Graphs and Bases for the Matching Lattice

✍ Scribed by Marcelo H. de Carvalho; Cláudio L. Lucchesi; U.S.R. Murty

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 225 KB
• Volume: 85
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.2001.2090

✦ Synopsis

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. Lova ´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.