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. Bibliography: 10 titles.

Original languageEnglish
Pages (from-to)631-648
Number of pages18
JournalJournal of Mathematical Sciences (United States)
Volume215
Issue number6
Early online date10 May 2016
DOIs
StatePublished - 1 Jun 2016

    Scopus subject areas

  • Statistics and Probability
  • Mathematics(all)
  • Applied Mathematics

    Research areas

  • White Vertex, External Edge, Matching Number, Chip Removal, External Vertex

ID: 37050452