Maximal Matching Polynomials of Phenylene and Benzenoid Chains

Abstract

A matching in a graph refers to a collection of edges where no two edges share common endpoints.
A maximal matching (MM) of a graph is defined as a matching such that it is impossible to add any more edges to it within the graph to form a larger matching. The maximal matching polynomial (MMP) of a graph is the generating polynomial for the number of MMs of each size.
In this article, through the employment of the transfer matrix technique, we first present formulas for calculating the MMPs of phenylene and benzenoid chains. Subsequently, computational formulas for the number of MMs of phenylene and benzenoid chains are derived.
Moreover, we determine the expected values of the number of MMs for random phenylene and benzenoid chains.