DROPS

Document

DOI: 10.4230/LIPIcs.WG.2026.28

Lower Bounds for the Pfaffian Number of Graphs

Authors: Enrique Junchaya, Alberto Alexandre Assis Miranda, and Cláudio Leonardo Lucchesi

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

Abstract

The number of perfect matchings of a k-pfaffian graph can be counted by computing a linear combination of the pfaffians of k matrices. The pfaffian number of a graph G is the smallest integer k such that G is k-pfaffian. We present the first known lower bounds for the pfaffian number of graphs. As an intermediate step, we prove an upper bound for the rank of two matrices related to their Khatri-Rao product. One of the consequences of the found lower bounds is the existence of graphs whose pfaffian numbers are arbitrarily large.

Cite as

Enrique Junchaya, Alberto Alexandre Assis Miranda, and Cláudio Leonardo Lucchesi. Lower Bounds for the Pfaffian Number of Graphs. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{junchaya_et_al:LIPIcs.WG.2026.28,
  author =	{Junchaya, Enrique and Assis Miranda, Alberto Alexandre and Lucchesi, Cl\'{a}udio Leonardo},
  title =	{{Lower Bounds for the Pfaffian Number of Graphs}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{28:1--28:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.28},
  URN =		{urn:nbn:de:0030-drops-261946},
  doi =		{10.4230/LIPIcs.WG.2026.28},
  annote =	{Keywords: Perfect matchings, pfaffian graphs, k-pfaffian graphs, pfaffian number of graphs}
}

Search Results

Documents authored by Assis Miranda, Alberto Alexandre

Lower Bounds for the Pfaffian Number of Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message