Chip Removal. Urban Renewal Revisited

被引：0

作者：

Aksenov V. ^{[1
]}

Kokhas K. ^{[1
]}

机构：

[1] ITMO University, St.Petersburg

来源：

Journal of Mathematical Sciences | 2015年 / 209卷 / 6期

关键词：

Adjacency Matrix; Chebyshev Polynomial; Urban Renewal; Outgoing Edge; Adjacency Matrice;

D O I：

10.1007/s10958-015-2528-9

中图分类号：

学科分类号：

摘要：

We describe a new combinatorial-algebraic transformation on graphs which we call the “chip removal.” It generalizes the well-known urban renewal trick of Propp and Kuperberg. The chip removal is useful in calculations of the determinants of adjacency matrices and matching numbers of graphs. A beautiful example of applying this technique is a theorem on removing 4-contact chips, which generalizes Kuo’s graphical condensation method. Numerous examples are given. Bibliography: 6 titles. © 2015, Springer Science+Business Media New York.

引用

页码：809 / 825

页数：16

共 5 条

[1]

Aksenov V., Kokhas K., Domino tilings and determinants, J. Math. Sci., 200, 6, pp. 647-653, (2014)

[2]

Ciucu M., Enumeration of perfect matchings in graphs with reflective symmetry, J. Combin. Theory Ser. A, 77, 1, pp. 67-97, (1997)

[3]

Kuo E., Application of graphical condensation for enumerating matchings, Theoret. Comput. Sci., 319, pp. 29-57, (2004)

[4]

Propp J., Generalized domino-shuffling, Theoret. Comput. Sci., 303, 2-3, pp. 267-301, (2003)

[5]

Rara H.M., Reduction procedures for calculating the determinant of the adjacency matrix of some graphs and the singularity of square planar grids, Discrete Math., 151, pp. 213-219, (1996)

← 1 →