Authors: Al-Yakoob, Salem
Kanso, Ali
Stevanović, Dragan 
Affiliations: Mathematics 
Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: On Hosoya’s dormants and sprouts
Journal: Applied Mathematics and Computation
Volume: 430
First page: 127233
Issue Date: 2022
Rank: M21a
ISSN: 0096-3003
DOI: 10.1016/j.amc.2022.127233
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.
Keywords: Cospectral graphs | Characteristic polynomial | Multiple coalescences | Computational enumeration
Publisher: Elsevier

Show full item record

Page view(s)

checked on Sep 15, 2022

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.