Please use this identifier to cite or link to this item:

`http://repositorio.unicamp.br/jspui/handle/REPOSIP/79715`

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 |

Rights: | fechado |

Identifier DOI: | 10.1007/s004930050051 |

Date Issue: | 1999 |

Appears in Collections: | Unicamp - Artigos e Outros Documentos |

Files in This Item:

File | Description | Size | Format | |
---|---|---|---|---|

WOS000082196000001.pdf | 314.51 kB | Adobe PDF | View/Open |

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