2014/04/20 by Mihai Ciucu, Ciucu, Mihai · 1 citation
Computer Science · Engineering · #05A15 #05A19 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1404.5003
openalex publication_date 2014/04/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.