The Restricted-Subduced-Cycle-Index (RSCI) Method for Counting Matchings of Graphs and Its Application to Z-Counting Polynomials and the Hosoya Index as Well as to Matching Polynomials

摘要

The restricted-subduced-cycle-index (RSCI) method for generating Z-counting polynomials and the Hosoya indices (Z-indices) as well as matching polynomials has been developed by starting from subduced cycle indices (SCI) defined in the unit-subduced-cycle-index (USCI) approach (S. Fujita, Symmetry and Combinatorial Enumeration in Chemistry, Springer-Verlag, 1991). In the RSCI method, k-matchings of a given skeleton (or graph) for deriving these matters are regarded as restricted structures in which vertex substitution and edge substitution occur concurrently under a restricted condition that occupation of a common vertex does not occur. For the purpose of counting such restricted structures, the concepts of territory indicators and territory discriminants are introduced. Thereby, an RSCI for the skeleton (or graph) is derived from an SCI by the subduction to C-1 (nonsymmetry). The RSCI gives the generating function for counting the numbers of restricted structures, which is further converted into a Z-counting polynomial, the Hosoya indices, as well as a matching polynomial. The versatility of the RSCI method is illustrated by applying to benzene, naphthalene, dodecahedron, and fullerene C-60.