Counting perfect matchings in n-extendable graphs |
| |
| Authors: | Tomislav Došli? |
| |
| Institution: | Department of Mathematics, Faculty of Civil Engineering, University of Zagreb, Ka?i?eva 26, 10000 Zagreb, Croatia |
| |
| 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)!/4q-p-(n-1)(2Δ-3)+4]⌉ different perfect matchings, where Δ is the maximum degree of a vertex in G. |
| |
| Keywords: | 05C70 05C40 05C75 |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
