|
Zapiski Nauchnykh Seminarov 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.
Received: 23.09.2015
Citation:
O. V. Bursian, “Chip removal for computing the number of perfect matchings”, Representation theory, dynamical systems, combinatorial and algoritmic methods. Part XXVI. Representation theory, dynamical systems, combinatorial methods, Zap. Nauchn. Sem. POMI, 437, POMI, St. Petersburg, 2015, 62–80; J. Math. Sci. (N. Y.), 216:1 (2016), 41–52
Linking options:
https://www.mathnet.ru/eng/znsl6173 https://www.mathnet.ru/eng/znsl/v437/p62
|
Statistics & downloads: |
Abstract page: | 133 | Full-text PDF : | 32 | References: | 34 |
|