pith. sign in

arxiv: 1404.5003 · v1 · pith:S25IANTZnew · submitted 2014-04-20 · 🧮 math.CO

A generalization of Kuo condensation

classification 🧮 math.CO
keywords condensationformulaobtainedperfectremovingverticesbipartitedistinguished
0
0 comments X
read the original abstract

Kuo introduced his 4-point condensation in 2003 for bipartite planar graphs. In 2006 Kuo generalized this 4-point condensation to planar graphs that are not necessarily bipartite. His formula expressed the product between the number of perfect matching of the original graph $G$ and that of the subgraph obtained from $G$ by removing the four distinguished vertices as a Pfaffian of order 4, whose entries are numbers of perfect matchings of subgraphs of $G$ obtained by removing various pairs of vertices chosen from among the four distinguished ones. The compelling elegance of this formula is inviting of generalization. Kuo generalized it to $2k$ points under the special assumption that the subgraph obtained by removing some subset of the $2k$ vertices has precisely one perfect matching. In this paper we prove that the formula holds in the general case. We also present a couple of applications.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.