Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: Ear decompositions of matching covered graphs
Author: Carvalho, MH
Lucchesi, CL
Murty, USR
Abstract: Ear decompositions of matching covered graphs are important for understanding their structure. By exploiting the properties of the dependence relation introduced by Carvalho and Lucchesi in [2], we are able to provide simple proofs of several well-known theorems concerning ear decompositions. Our method actually provides proofs of generalizations of these theorems. For example, we show that every matching covered graph G different from K-2 and C-2n has at least Delta edge-disjoint removable ears, where Delta is the maximum degree of G. This shows that any matching covered graph G has at least Delta! different ear decompositions, and thus is a generalization of the fundamental theorem of Lovasz and Plummer establishing the existence of ear decompositions. We also show that every brick G different from K-4 and (C) over bar(6) has Delta-2 edges, each of which is a removable edge in G, that is, an edge whose deletion from G results in a matching covered graph. This generalizes a well-known theorem of Lovasz. We also give a simple proof of another theorem due to Lovasz which says that every nonbipartite matching covered graph has a canonical ear decomposition, that is, one in which either the third graph in the sequence is an odd-subdivision of K-4 or the fourth graph in the sequence is an odd-subdivision of (C) over bar(6). Our method in fact shows that every nonbipartite matching covered graph has a canonical ear decomposition which is optimal, that is one which has as few double ears as possible. Most of these results appear in the Ph. D. thesis of the first author [1], written under the supervision of the second author.
Country: Hungria
Editor: Janos Bolyai Mathematical Soc
Citation: Combinatorica. Janos Bolyai Mathematical Soc, v. 19, n. 2, n. 151, n. 174, 1999.
Rights: fechado
Identifier DOI: 10.1007/s004930050051
Date Issue: 1999
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000082196000001.pdf314.51 kBAdobe PDFView/Open

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