The Number of Maximal Matchings in Polyphenylene Chains

Document Type : Research Paper


Department of Mathematics, Grand Valley State University, Allendale, MI, USA


A matching is maximal if no other matching contains it as a proper subset. Maximal matchings model phenomena across many disciplines, including applications within chemistry. In this paper, we study maximal matchings in an important class of chemical compounds: polyphenylenes. In particular, we determine the extremal polyphenylene chains in regards to the number of maximal matchings. We also determine recurrences and generating functions for the sequences enumerating maximal matchings in several specific types of polyphenylenes and use these results to analyze the asymptotic behavior.



    1. S. J. Cyvin and I. Gutman, Kekulé Structures in Benzenoid Hydrocarbons, Lecture Notes in Chemistry 46, Springer, Heidelberg, 1988.
    2. L. Lovász and M. D. Plummer, Matching Theory, North-Holland, Amsterdam, 1986.
    3. W. Goddard and M. A. Henning, Independent domination in graphs: A survey and recent results, Discrete Math.313 (2013) 839–854.
    4. P. J. Flory, Intramolecular reaction between neighboring substituents of vinyl polymers, J. Am. Chem. Soc. 61 (1939) 1518–1521.
    5. T. Došlić, Block Allocation of a sequential resource, Ars. Math. Contemp. 17 (2019) 79−88.
    6. T. Došlić and I. Zubac, Counting maximal matchings in linear polymers, Ars. Math. Contemp. 11 (2016) 255–276.
    7. T. Došlić and T. Short, Maximal matchings in polyspiro and benzenoid chains, arXiv:1511.00590.
    8. T. Došlić and I. Zubac, Saturation number of benzenoid graphs, MATCH Commun. Math. Comput. Chem. 73 (2015) 491–500.
    9. V. Andova, F. Kardoš and R. Škrekovski, Sandwiching the saturation number of fullerene graphs, MATCH Commun. Math. Comput. Chem. 73 (2015) 501–518.
    10. T. Došlić, Saturation number of fullerene graphs, J. Math. Chem. 43 (2008) 647–657.
    11. T. Short, The saturation number of carbon nanocones and nanotubes, MATCH Commun. Math. Comput. Chem. 82 (2019) 181–201.
    12. N. Tratnik and P. Ž Pleteršek, Saturation number of nanotubes, Ars Math. Contemp. 12 (2017) 337–350.
    13. T. Došlić and M. S. Litz, Matchings and independent sets in polyphenylene chains, MATCH Commun. Math. Comput. Chem. 67 (2012) 313–330.
    14. F. J. Zhang and M. K. Zhou, Matching polynomials of two classes of graphs, Discrete Appl. Math. 20 (1988) 253–260.
    15. D. B. West, Introduction to Graph Theory, Prentice Hall, Upper Saddle River, 1996.
    16. H. S. Wilf, Generatingfunctionology, Academic Press, 1990.