A Pfaffian formula for matching polynomials of outerplanar graphs. (4th May 2021)

• Record Type: Journal Article
• Authors: Iwata, Satoru
• Is Part Of: Optimization methods and software. Volume 36:Number 2/3(2021)
• Page Start: 332
• Page End: 336
• Publication Date: 2021-05-04
• Subjects: 05C30; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2020.1769620
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : An outerplanar graph is a graph that can be drawn on the plane without crossing edges so that all vertices are on the infinite face. Most organic compounds have outerplanar graph structures. The number of matchings in the skeleton graphs of organic compounds is known as the topological index Z, introduced in the early 70s to investigate correlation between molecular structures and physical properties. This paper provides a simple formula that expresses the number of matchings, and more generally the matching polynomial, of an outerplanar graph by the Pfaffian of a certain skew-symmetrc matrix.