Name
Abstract | ||
|---|---|---|
We prove that every $n$-vertex cubic bridgeless graph has at least $n/2$ perfect matchings and give a list of all 17 such graphs that have less than $n/2+2$ perfect matchings. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1137/080723843 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
vertex cubic bridgeless graph,perfect matchings,new lower bound,cubic graphs,perfect matching,cubic graph,lower bound | Discrete mathematics,Combinatorics,Upper and lower bounds,Vertex (graph theory),Cubic graph,Tutte theorem,Matching (graph theory),Decomposition method (constraint satisfaction),Trivially perfect graph,Mathematics,Strong perfect graph theorem | Journal |
Volume | Issue | ISSN |
23 | 3 | 0895-4801 |
Citations | PageRank | References |
8 | 1.68 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daniel Král' | 1 | 426 | 46.78 |
| Jean-Sébastien Sereni | 2 | 269 | 28.69 |
| Michael Stiebitz | 3 | 207 | 30.08 |