Premium
Graphs with independent perfect matchings
Author(s) -
de Carvalho Marcelo H.,
Lucchesi Cláudio L.,
Murty U. S. R.
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20036
Subject(s) - combinatorics , mathematics , perfect graph theorem , strong perfect graph theorem , perfect graph , trivially perfect graph , matching (statistics) , discrete mathematics , line graph , graph , pathwidth , statistics
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. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 19–50, 2005