Matching signatures and Pfaffian graphs |
| |
Authors: | Alberto Alexandre Assis Miranda Cláudio Leonardo Lucchesi |
| |
Institution: | aInstitute of Computing, University of Campinas, 13084-971 Campinas, SP, Brazil;bFACOM-UFMS, 79070-900 Campo Grande, MS, Brazil |
| |
Abstract: | Perfect matchings of k-Pfaffian graphs may be enumerated in polynomial time on the number of vertices, for fixed k. In general, this enumeration problem is #P-complete. We give a Composition Theorem of 2r-Pfaffian graphs from r Pfaffian spanning subgraphs. Constructions of k-Pfaffian graphs known prior to this seem to be of a very different and essentially topological nature. We apply our Composition Theorem to produce a bipartite graph on 10 vertices that is 6-Pfaffian but not 4-Pfaffian. This is a counter-example to a conjecture of Norine (2009) 8], which states that the Pfaffian number of a graph is a power of four. |
| |
Keywords: | Pfaffian graphs Perfect matchings Matching covered graphs |
本文献已被 ScienceDirect 等数据库收录! |
|