• Title of article

    Matching signatures and Pfaffian graphs

  • Author/Authors

    Miranda، نويسنده , , Alberto Alexandre Assis and Lucchesi، نويسنده , , Clلudio Leonardo، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2011
  • Pages
    6
  • From page
    289
  • To page
    294
  • 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 2 r -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
    Perfect matchings , Pfaffian graphs , matching covered graphs
  • Journal title
    Discrete Mathematics
  • Serial Year
    2011
  • Journal title
    Discrete Mathematics
  • Record number

    1599566