Abstract:
We describe a new combinatorial-algebraic transformation on graphs which we call “chip removal.” It generalizes the well-known Urban Renewal trick of Propp and Kuperberg. The chip removal is useful in calculations of determinants of adjacency matrices and matching numbers of graphs. A beautiful example of this technique is a theorem on removing four-contact chips, which generalizes Kuo's graphical condensation method. Numerous examples are given.
Key words and phrases:determinant of adjacency matrix, matching number, “Urban Renewal”, pfaffian, combinatorial linear algebra.