Artículos de revistas
Ear decompositions of matching covered graphs
Registro en:
Combinatorica. Janos Bolyai Mathematical Soc, v. 19, n. 2, n. 151, n. 174, 1999.
0209-9683
WOS:000082196000001
10.1007/s004930050051
Autor
Carvalho, MH
Lucchesi, CL
Murty, USR
Institución
Resumen
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. 19 2 151 174