Plenary Lecture

A Tribute to Sylvester: “Chemicographic” Representation of the Graph Matching Polynomial

Professor Remi Chauvin
Laboratory of Coordination Chemistry
Toulouse 3-Paul Sabatier University

Abstract: The matching polynomial m(x) of a graph G0 of order n, i.e. the generating function of the numbers mk of k-edge matchings of G0, receives several types of applications in chemistry: considereing molecular graphs, it is thus invoked in either contexts of combinatoric analysis (definitions of indices for empirical structure-property relationships and chemoinformatic applications) or spectral analysis (generalization of the notion of “graph energy”). In the latter context, the matching polynomial has played a historical role by lifting the fuzziness of the notion of “aromaticity” (the effect of the cyclic character of the molecular graph on stability): in 1976, Aihara,[1] and Milun, Trinasjstic and Gutman[2] simultaneously showed that in the topological limit, aromaticity is exactly quantified by the “topological resonance energy”, defined from the roots of the characteristic polynomial P0(x) of G0, and those (all real) of the corresponding acyclic polynomial Pac(x) = xn m(–x–2), for which a systematic graph interpretation was lacking.
From the Sachs theorem, the matching polynomial of a forest graph is the characteristic polynomial of a graph Gac = G0. A long-standing issue has thus been whether a similar representation of the acyclic polynomial could be generalized for cyclic graphs (with Gac ≠ G0). After 36-years, the acyclic polynomial has been finally given an indirect interpretation -as a sum of characteristic polynomials-,[3] and a direct representation as the secular determinant of a “chemicograph” Gac, in the Sylvester’definition of 1878.[4] Gac is actually the graph of “twisting ring-opening-ring-closing metathesis product” of the molecule, resulting from “differential duplexation” (“roc product“®) and Möbius-twist (–1 edge-weighting) of G0.[5]

[1] J. Aihara, A New Definition of Dewar-Type Resonance Energies, Journal of the American Chemical Society, Vol. 98, No. 10, 1976, 2750-2758.
[2] I. Gutman, M. Milun, N. Trinajstic, Graph Theory and Molecular Orbitals. XVIII. On Topological Resonance Energy, Croatica Chemica Acta, Vol. 48, 1976, pp. 87-95.
[3] R. Chauvin, C. Lepetit, P. W. Fowler, J. P. Malrieu, The Chemical Roots of the Matching Polynomial, Physical Chemistry Chemical Physics, Vol. 12, 2010, pp. 5295-5306.
[4] R. Chauvin, C. Lepetit, The Fundamental Chemical Equation of Aromaticity, Physical Chemistry Chemical Physics, Vol. 15, 2013, pp. 3855-3860.
[5] J. J. Sylvester, Chemistry and Algebra, Nature, Vol. 17, 1878, p. 284.

Brief Biography of the Speaker: After graduate studies in mathematics and chemistry, in 1988 he received a Ph.D. in chemistry and more precisely in the field of molecular chirality and asymmetric catalysis, under the supervision of Prof. H. B. Kagan in Orsay (France). He pursued as a post-doctoral fellow at MIT (USA) first, and then in Zürich (Switzerland) with Prof. A. Vasella. Back to France, he worked at the Roussel Uclaf company in Romainville, and by the end of 1993 came back to the academic research at the CNRS in Toulouse. In 1998, he was appointed full Professor at the Paul Sabatier University and launched a new research group at the Laboratory of Coordination Chemistry. Today author of 134 publications and running research in two different laboratories, he is involved in three experimental fields (organometallic chemistry of chiral phospho-carbon ligands, organic chemistry of functional carbo-mer molecules, organic synthesis of anti-tumoral compounds) and in several aspects of theoretical and mathematical chemistry. Beyond molecular modeling, his special focus on the continuous quantification of discrete qualitative properties (bonding, symmetry, chirality, aromaticity,...), led him to get involved in various domains of chemical mathematics, and more particularly today in spectral graph theory.