Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/68438
Type: Artigo de periódico
Title: Graphs with independent perfect matchings
Author: de Carvalho, MH
Lucchesi, CL
Murty, USR
Abstract: A graph with at least two vertices is matching covered if it is connected and each edge lies in some perfect matching. A matching covered graph G is extremal if the number of perfect matchings of G is equal to the dimension of the lattice spanned by the set of incidence vectors of perfect matchings of G. We first establish several basic properties of extremal matching covered graphs. In particular, we show that every extremal brick may be obtained by splicing graphs whose underlying simple graphs are odd wheels. Then, using the main theorem proved in [2] and [3], we find all the extremal cubic matching covered graphs. (C) 2004 Wiley Periodicals, Inc.
Subject: graphs
perfect matchings
matching lattice
Country: EUA
Editor: John Wiley & Sons Inc
Rights: fechado
Identifier DOI: 10.1002/jgt.20036
Date Issue: 2005
Appears in Collections:Artigos e Materiais de Revistas Científicas - Unicamp

Files in This Item:
File Description SizeFormat 
WOS000225719000002.pdf240.66 kBAdobe PDFView/Open


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