Total Independent Set Numbers on Catacondensed Polyomino Systems

Abstract

A catacondensed polyomino system is a chain polyomino system in which the joining of the centers of its adjacent cells forms a tree. Total independent set number is a graph invariant that has been studied extensively in statistical mechanics and mathematical chemistry. In this paper, we introduce a new graph vector at a given edge and get some recurrence relations on the total independent set numbers of the path-like polyomino systems. Based on these relations, the reduction formulas of computing the total independent set number of any catacondensed polyomino system via transfer matrices can be obtained.