Seminar za biomatematiko in matematično kemijo - Arhiv

The cut method has an important role in the investigation of molecular descriptors. Very often it was applied to benzenoid systems to efficiently compute distance-based topological indices, for example the Wiener index and the Szeged index. Later, the cut method was generalized such that it can be used on any connected graph by using Djoković-Winkler relation. In this talk, we present the cut method for the edge version of the Wiener index and for an infinite family of Szeged-like topological indices.

In the first part, we focus on the edge-Wiener index, which is for any connected graph G defined as the Wiener index of the line graph of G. We show that the edge-Wiener index of an edge-weighted graph can be computed in terms of the three Wiener indices of weighted quotient graphs. Thus, already known analogous methods for computing the edge-Wiener index of benzenoid systems and phenylenes are generalized.

In the second part, we formally introduce the concept of a general Szeged-like topological index, which includes many well known topological indices (for example Szeged, PI and Mostar indices) and also infinitely many other topological indices that can be defined in a similar way. As the main result, we provide a cut method for computing a general Szeged-like topological index for any connected strength-weighted graph. This greatly generalizes various methods known for some of the mentioned indices.

Join Zoom Meeting HERE!

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. After briefly surveying the history of constructing cospectral graphs, we focus on the expectations and questions about cospectrality of multiple coalescences that were raised in Hosoya's papers. In particular, we discuss the characteristic polynomial of such multiple coalescences, from which a necessary and sufficient condition for their cospectrality follows. 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.

Join Zoom Meeting HERE!