| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4650524 | Discrete Mathematics | 2008 | 4 Pages |
Abstract
The structural theory of matchings is used to establish lower bounds on the number of perfect matchings in n-extendable graphs. It is shown that any such graph on p vertices and q edges contains at least ⌈(n+1)!/4[q-p-(n-1)(2Δ-3)+4]⌉⌈(n+1)!/4[q-p-(n-1)(2Δ-3)+4]⌉ different perfect matchings, where ΔΔ is the maximum degree of a vertex in G.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Tomislav Došlić,