On Hosoya’s dormants and sprouts

Abstract

The study of cospectral graphs is one of the traditional topics of spectral graph theory. Initial expectation by theoretical chemists Günthard and Primas in 1956 that molecular graphs are characterized by the multiset of eigenvalues of the adjacency matrix was quickly refuted by the existence of numerous examples of cospectral graphs in both chemical and mathematical literature. This work was further motivated by Fisher in 1966 in the influential study that investigated whether one can “hear” the shape of a (discrete) drum, which has led over the years to the construction of many cospectral graphs. These findings culminated in setting the ground for the Godsil-McKay local switching and the Schwenk’s use of coalescences, both of which were used to show (around the 1980s) that almost all trees have cospectral mates. Recently, enumerations of cospectral graphs with up to 12 vertices by Haemers and Spence and by Brouwer and Spence have led to the conjecture that, on the contrary, “almost all graphs are likely to be determined by their spectrum”. This conjecture paved the way for myriad of results showing that various special types of graphs are determined by their spectra.

On the other hand, in a recent series of papers, Hosoya drew the attention to a particular aspect of constructing cospectral graphs by using coalescences: that cospectral graphs can be constructed by attaching multiple copies of a rooted graph in different ways to subsets of vertices of an underlying graph. The principal focus of this research effort is to address the expectations and questions raised in Hosoyas papers. We give an explicit formula for the characteristic polynomial of such multiple coalescences, from which we obtain a necessary and sufficient condition for cospectrality of these coalescences. We enumerate such pairs of cospectral multiple coalescences for a few families of underlying graphs, and show the infinitude of cospectral multiple coalescences having paths as underlying graphs, which were deemed rare by Hosoya.