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!

A nut graph is a simple graph whose adjacency matrix has the eigenvalue 0 with multiplicity 1 such that its corresponding eigenvector has no zero entries. Motivated by a question of Fowler et al. [Discuss. Math. Graph Theory 40 (2020), 533–557] to determine the pairs (n, d) for which a vertex-transitive nut graph of order n and degree d exists, Bašić et al. [arXiv:2102.04418, 2021] initiated the study of circulant nut graphs. Here we first show that the generator set of a circulant nut graph necessarily contains equally many even and odd integers. Then we characterize circulant nut graphs with the generator set {x, x + 1, …, x + 2t − 1} for x, t ∈ ℕ, which generalizes the result of Bašić et al. for the generator set {1, …, 2t}. We further study circulant nut graphs with the generator set {1, …, 2t + 1} \ {t}, which yields nut graphs of every even order n ≥ 4t + 4 whenever t is odd such that t ≠ 1 (mod 10) and t ≠ 15 (mod 18). This fully resolves Conjecture 9 from Bašić et al. [ibid.]. We also study the existence of 4t-regular circulant nut graphs for small values of t, which partially resolves Conjecture 10 of Bašić et al. [ibid.].

While the original question is stated in terms of (spectral) graph theory, the talk will very quickly move from the setting of graph eigenvalues and eigenvectors to polynomial algebra, with most of the obtained results based on the properties of cyclotomic polynomials.

This is a joint work with Ivan Damnjanović.

Join Zoom Meeting HERE!

Nanotubical graphs are obtained by wrapping a hexagonal grid into a cylinder, and then possibly closing the tube with patches. Here we consider the asymptotic values of Wiener, generalized Wiener, Schultz (also known as degree distance), Gutman, Balaban, Sum-Balaban, and Harary indices for (all) nanotubical graphs of type (k, l) on n vertices. First, we determine the number of vertices at distance d from a particular vertex in an open (k, l) nanotubical graph. Surprisingly, this number does not depend much on the type of the nanotubical structure, but mainely on its circumference. At the same time, the size of a cap of a closed (k, l)-nanotube is bounded by a function that depends only on k and l, and that those extra vertices of the caps do not influence the obtained asymptotical value of the distance based indices considered here. Consequently the asymptotic values are the same for open and closed nanostructures. Finally, we obtained that the leading term of all considered topological indices depends on the circumference of the nanotubical graph, but not on its specific type. Thus, we conclude that these distance based topological indices seem not to be the most suitable for distinguishing nanotubes with the same circumference and of different type as far as the leading term is concerned.

Join Zoom Meeting HERE!

The canonical double cover (CDC) of a graph G is the direct product G × K₂. Graphs with the same CDC share the same walk matrix but not necessarily the same main eigenvalues or eigenvectors that determine the number of walks between pairs of vertices. We explore a new concept to see to what extent the main eigenspace determines the entries of the walk matrix of a graph. We establish a hierarchy of inclusions connecting classes of graphs in view of their CDC, walk matrix, main eigenvalues and main eigenspaces. We provide a new proof that graphs with the same CDC have two–fold symmetry and are characterized as TF-isomorphic graphs. In the source and sink potential (SSP) model, current flowing through the bonds of a Pi system molecule, from the source atom to the sink one, may choose a shortest path or may take a longer route, possibly flowing along the edges of cycles. Molecular electronic devices with the same CDC are likely to offer the same resistance to current flow for corresponding terminals.

Keywords: bipartite (canonical) double covering, main eigenspace, comain graphs, walk matrix, two-fold isomorphism, SSP model.

Join Zoom Meeting HERE!

A perfect packing of a graph H into a graph G is a spanning subgraph of G whose every component is isomorphic to H. We consider several small graphs H and investigate which fullerene graphs allow such packings. We also consider generalized fullerene graphs and packings of small graphs into classical and generalized fullerenes which are not perfect.

Join Zoom Meeting HERE!

Finding solutions for problems in chemistry and biology often entails the enumeration of objects within a combinatorial class. Examples include the design space of self-assembling protein or DNA strands and the chemical spaces spanned by a set of chemical reactions modelled as graph transformation rules. Naturally, canonicalisation of objects allows for achieving highly efficient implementations to solve the underlying problem. We will present algorithms, their implementations, and empirical results for

1. state-of-the-art canonicalisation of chemical graphs as well as for
2. a large-scale enumeration of non-isomorphic 1-face embeddings.

The latter includes pruning techniques based on a novel invariant called bio gap. The likelihood of two segments to bind in a biochemical setting depends on their proximity, and it is conceivable that the proximity might be reflected by the biological gap representation.

Join Zoom Meeting HERE!

Reconciliations of trees, that is, mappings μ: V(T) → V(S) ∪ E(S) from a rooted tree T, the gene tree, into another tree S, the species tree, with a given correspondence between the leaves describes e.g. the evolution of gene families or the co-evolution of hosts and parasites. Here we consider both trees “timed”, i.e., vertices u of T and x of S is associated with a timestamp τ_T(u) and τ_S(x) that respect the ancestor order of the trees and satisfy τ_T(v) = τ_S(μ(v)). Horizontal transfer corresponds to edges xy ∈ E(T) such that μ(x) and μ(y) are uncomparable w.r.t. the ancestor order in S. The identification of horizontal transfer events is a difficult problem in practical data analysis. An approach used in practise is to consider pairs of leaves (u, v) in T such that the last common ancestor of the species σ(u) and σ(v) is older than the last common ancestor of u and v. This defines a (colored, undirected) graph, the Later Divergence Time (LDT) graph, which can be estimated from data.

The presentation will be concerned with the characterization of the class of LDT graph and ask how much information on S, T, μ can be retrieved from a given LDT. We shall see that LDT graphs are properly colored cographs and determine certain “informative” sets of rooted triples that are displayed and T and S, respectively. The LDT graph, furthermore, is a subgraph of the Fitch graph, that is the graph whose edges are the pair of genes that are separated by a horizontal transfer event, in general however, it does not identify all horizontal transfer events.

Join Zoom Meeting HERE!

Horizontal Gene Transfer (HGT) is the movement of genetic material between coexisting species. Given the true history of the genes, Walter M. Fitch defined in his illuminating paper [Trends Genet. 16 (2000) 227–231, doi:10.1016/s0168-9525(00)02005-9] two genes as “xenologs” if their history since their common ancestor involves HGT of at least one of them. Although this definition of xenology is one of the most commonly used terms in phylogenomics, the mathematics of the xenology-relation X has not been investigated in detail, so-far. In this talk, we consider the following two problems:

1. How much phylogenetic signal is contained in a xenology-relation X? In other words, is it possible to infer phylogenetic trees from X? 
2. Can we characterize xenology-relations? In other words, is it possible to decide whether an arbitrary binary relation is a xenology-relation? 

To this end, we study the graph structure of the relation X. Surprisingly, xenology-relations are characterized by a small set of forbidden induced subgraphs on three vertices and they form a subclass of so-called directed cographs. We provide a linear-time algorithm to recognize such relations and for the reconstruction of least-resolved phylogenetic trees.

Join Zoom Meeting HERE!

The simplest description of conjugated hydrocarbons is Hückel Molecular Orbital (HMO) Theory, which is in essence a graph theoretical model. Eigenvectors and eigenvalues of the adjacency matrix of the molecular graph are used to model spatial distributions and energies of the mobile electrons that dominate the chemical and physical properties of these important unsaturated systems. Charles Alfred Coulson FRS (1910 – 1974) was a leading figure in the development and exploitation of HMO theory from the early 1940s all the way through to the 1970s. His work with Longuet-Higgins defined key concepts that still shape chemical thinking about benzenoids and have found new applications with the many forms of carbon that have emerged in the decades since his death. This talk will discuss a claim that surfaced in Coulson’s early work, is part of the folklore of HMO theory apparently believed by all chemists, but until recently had no complete published proof, despite tantalising hints sprinkled through 70 years of primary literature and textbooks.

This talk is based on J. Chem. Phys. 151 (2019) 151101, doi:10.1063/1.5128624 but also covers some more recent developments.

Join Zoom Meeting HERE!