RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2015 Volume 437, Pages 62–80 (Mi znsl6173)

Chip removal for computing the number of perfect matchings

O. V. Bursian

St. Petersburg State University, St. Petersburg, Russia

Abstract: We consider a transformation of a graph $G$ that replaces an induced subgraph $H$ of arbitrary size by a little new subgraph $h$. We choose $h$ in such a way that the equality $M(G)=xM(G')$ holds (where $G'$ is the new graph and the factor $x$ depends on the numbers of matchings of $H$ and its subgraphs). We describe how one can construct $h$ when $G$ is a planar graph and $H$ is a bipartite graph (with some restriction on the coloring of vertices connecting it with the other part of the graph $G$). For a planar bipartite graph $H$ with a small number of such vertices, we prove that the equality holds for an arbitrary graph $G$.

Key words and phrases: matching number, “Urban renewal”, Pfaffian.

UDC: 519.148+519.177.3+519.172.2

Received: 23.09.2015


 English version:
Journal of Mathematical Sciences (New York), 2016, 216:1, 41–52

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024