Upper Bounds for Perfect Matchings in Pfaffian and Planar Graphs

  • Afshin Behmaram
  • Shmuel Friedland
DOI: https://doi.org/10.37236/2845
Keywords: Perfect matchings, pfaffian graphs, fullerene graphs, Hadamard's determinant inequality

Abstract

We give upper bounds on weighted perfect matchings in Pfaffian graphs. These upper bounds are better than Bregman's upper bounds on the number of perfect matchings. We show that some of our upper bounds are sharp for 3 and 4-regular Pfaffian graphs. We apply our results to fullerene graphs.
Published
2013-03-24
How to Cite
Behmaram, A., & Friedland, S. (2013). Upper Bounds for Perfect Matchings in Pfaffian and Planar Graphs. The Electronic Journal of Combinatorics, 20(1), P64. https://doi.org/10.37236/2845
Issue
Volume 20, Issue 1 (2013)
Article Number
P64