Seminar za biomatematiko in matematično kemijo

The transmission of a vertex in a connected graph is the sum of its distances to all the other vertices. A graph is transmission irregular (TI) when all of its vertices have mutually distinct transmissions. In an earlier paper, Al-Yakoob and Stevanović [Appl. Math. Comput. 380 (2020), 125257] gave the full characterization of TI starlike trees with three branches. Here, we improve these results by using a different approach to provide the complete characterization of all TI starlike trees and all TI double starlike trees. We subsequently implement the aforementioned conditions in order to find several infinite families of TI starlike trees and TI double starlike trees. Besides that, we disclose five families of unicyclic graphs with two pendent paths whose members are TI under certain conditions. As a direct consequence, we demonstrate the existence of TI chemical graphs of almost all even orders, thereby resolving a problem recently posed by Xu, Tian and Klavžar [Discrete Appl. Math. 340 (2023), 286–295].

Join Zoom Meeting HERE!

We characterize plane bipartite graphs whose resonance graphs are daisy cubes, and therefore generalize related results on resonance graphs of benzenoid graphs, catacondensed even ring systems, as well as 2-connected outerplane bipartite graphs. Firstly, we show that if G is a plane elementary bipartite graph other than K₂, then the resonance graph of G is a daisy cube if and only if the Fries number of G equals the number of finite faces of G. Next, we extend the above characterization from plane elementary bipartite graphs to plane bipartite graphs and show that the resonance graph of a plane bipartite graph G is a daisy cube if and only if G is weakly elementary bipartite such that each of its elementary component G_i other than K₂ holds the property that the Fries number of G_i equals the number of finite faces of G_i. Along the way, we provide a structural characterization for a plane elementary bipartite graph whose resonance graph is a daisy cube, and show that a Cartesian product graph is a daisy cube if and only if all of its nontrivial factors are daisy cubes.

Join Zoom Meeting HERE!

Adam Zsolt Wagner [arXiv:2104.14516] recently showed how reinforcement learning (RL) can be applied to construct (counter)examples in graph theory. We will showcase here a more readable, more stable and significantly faster reimplementation of his approach, and illustrate its work by finding counterexamples to a few published conjectures. We will also shortly discuss ways to implement several new RL environments that will cover constructions of simple graphs and trees, their signed variants, and graphs with bounded maximum vertex degree.

Join Zoom Meeting HERE!

Došlić et al. defined the Mostar index of a graph G as ∑_{uv ∈ E(G)} | n_G(u, v) - n_G(v, u) |, where, for an edge uv of G, the term n_G(u, v) denotes the number of vertices of G that are closer to u than to v. They also conjectured that Mostar index of G, Mo(G), is less or equal to 0.148 n³. In this talk we show that Mo(G) ≤ 0.1633 n³. If, however, G is bipartite, then we show that Mo(G) ≤ √3/18 n³, and that this bound is best possible up to terms of order O(n²).

This is joint work with Johannes Pardey, Dieter Rautenbach and Florian Werner from Ulm University.

Join Zoom Meeting HERE!

In 2012 we announced the House of Graphs (https://houseofgraphs.org/), which was a new database of graphs. The House of Graphs hosts complete lists of graphs of various graph classes, but its main feature is a searchable database of so called "interesting" graphs, which includes graphs that already occurred as extremal graphs or as counterexamples to conjectures. An important aspect of this database is that it can be extended by users of the website.

Over the years, several new features and graph invariants were added to the House of Graphs and users uploaded many interesting graphs to the website. But as the development of the original House of Graphs website started in 2010, the underlying frameworks and technologies of the website became outdated. This is why we completely rebuilt the House of Graphs using modern frameworks to build a maintainable and expandable web application that is future-proof. On top of this, several new functionalities were added to improve the application and the user experience.

In this talk we will present the House of graphs and highlight the changes and new features of the new website. We will also demonstrate how users can perform queries on this database and how they can add new interesting graphs to it.

Join Zoom Meeting HERE!

Chemical space is defined as the set of reported substances at a given time. It actually constitutes a space once the set is endowed with a notion of nearness.  There are at least two options for such a nearnees: substance's resemblance and chemical reachability.  The former is the basis of approaches boiling down to the concept of molecular similarity.  The latter is related to chemical reaction networks.  I will analyse in this talk the upper and lower bounds of the chemical space, the required memory space to store it and the possibilities for similarity studies in it.  I will also discuss the central role of directed hypergraphs for modelling the space, as well as the bounds for the number of hypergraphs.  Finally, I will discuss some features of the evolution of the chemical space and its implications for chemistry, as well as the opportunities for mathematics.

Join Zoom Meeting HERE!

Singular graphs of nullity one admitting a full kernel eigenvector are called nut graphs. Nut graphs constitute a fascinating family of graphs that has found many applications, in particular in mathematical chemistry. It has been promoted mostly by Irene Sciriha and her co-authors. Sciriha almost single-handedly laid down the fundamental theory of nut graphs. The emphasis of this talk is in the entries of the standard kernel eigenvector associated with a nut graph. Namely, the standard kernel eigenvector having the property that its integer entries have no non-trivial common factor is unique up to multiplication by -1.

In this talk we present some questions about nut graphs that have attracted researchers of this topic. We recall some tools that enable one to construct larger nut graphs from smaller ones. They explain some answers to these questions. We also ask some questions that may be of interest to some students.

This is a preparatory talk for another talk that will be delivered in Sombor, Serbia, in June 2022.

Join Zoom Meeting HERE!

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!

A fullerene is a 3-regular plane graph with only hexagonal and pentagonal faces, and models a pure carbon molecule. Nanotubes are a class of fullerenes that are cylindrical in shape and extremely useful in applications. The Clar number of a fullerene is a parameter related to its aromaticity and stability. In this talk, we partition nanotubes into two classes, those with relatively small and with relatively large Clar numbers. We describe the double bond structures, or perfect matchings, capable of forming in these two classes.

This is joint work with Jack Graver (Syracuse University) and Aaron Williams (Williams College).

Join Zoom Meeting HERE!

Let G be a finite simple undirected graph with n vertices and m edges. The energy of the graph G, denoted by E(G), is defined as the sum of the absolute values of all eigenvalues of G. In this talk we present some new bounds for E(G) in terms of n, m and the largest and smallest eigenvalues of G. A number of our results rely on the use of well-known inequalities.

This is joint work with Robert Jajcay and Ivan Gutman.

Join Zoom Meeting HERE!

Chemical reactions encode a wealth amount of information on the transformation of chemical substances. In this talk we will discuss how to mathematically model them at the level of atoms involved in the molecules interacting in the chemical reaction. Here molecules are regarded as graphs, whose transformation are modelled by rewriting rules acting upon the graph of starting materials and yielding the graph of products of the chemical reaction. Leaving aside reactions as ensembles of atoms and their transformations, reactions can also be modelled at the level of substances, where the important information is which starting materials relate to each other to produce the final products. Here, the model we use is that of directed hypergraphs.

As chemical reactions reported by chemists grow exponentially, the hypergraph representing them turns very large. In general, large networks are treated by devising statistics gauging several aspects of such structures, some statistics are, e.g. vertex degree distributions, centrality, and several others. Recently, curvature of edges and vertices has been incorporated to this statistics and we will show how the curvature can be extended to hypergraphs, which actually generalise graph results.

In the last part of the talk we will discuss open questions about the growth of chemical reaction networks and how to model them.

I will present basic facts about nut graphs and core graphs using four papers by Irene Sciriha. I will also give a demonstrtion of a short SageMath program that tests whether a given graph is a nut graph. The talk will be concluded by some questions about nut graphs.

Already in 1923 science confirmed that “the analysis of the mechanical effects of muscle excitements would be incomplete if only changes in muscle length were examined disregarding changes in muscle thickness”. Distortions of muscle contraction mechanics due to longitudinal signal pathways were recently overcame by the mechanomyographic methods, where one of them, the Tensiomyography is a non-invasive method for detecting skeletal muscle contractile properties using a linear displacement sensor. It was designed to assess skeletal muscle thickening and low frequency lateral oscillations of active skeletal muscle fibres during twitch contractions and overcomes the limitations of mechanomyographic methods (low signal to noise ratio; low reliability; complex measuring setup; the need for complex post-processing) and dynamometry (low signal to noise ratio; pain; signal distortion, muscle cross-talk). Since its first scientific publication in 1990 more than 100 SCI articles show its use and purpose: in the estimation of muscle composition; for evaluating muscle atrophy and tone; for measuring adaptation to different pathologies; for measuring adaptation to specific training; and for measuring muscle fatigue.

The lecture will focus on the presentation of the scientific background of the Tensiomyography as well as the motivation for its development. Furthermore, we will focus on reliability and validity studies, together with its applications. During the lecture many future directions of TMG-based research will be proposed, focusing on mathematical and medical grounds.

This is joint work with István Estélyi, Riste Škrekovski and Niko Tratnik.

Električno aktivnost, ki jo  živčne celice  generirajo v možganih, lahko merimo na površini glave s pomočjo kape z vgrajenimi elektrodami. S tem se ukvarja elektroencefalografija (EEG), ki je uporabna ne le pri kliničnem delu, ampak tudi pri raziskovanju različnih kognitivnih procesov. V predavanju predstavimo, kako lahko teorijo grafov uporabimo za analizo EEG podatkov. Učinkovitost grafovskega pristopa ilustriramo na primeru blage kognitivne motnje.

In 2013 Gradišar et al. (National Institute of Chemistry, Slovenia) successfully designed a self-assembly tetrahedral polypeptide called TET12. It is a linear chain of twelve peptides, separated by flexible links, such that certain pairs of peptides “glued” together and formed coiled coil dimers. The end result was a stable tetrahedron in which each of its six edges was a coiled coil dimer.

In the following years mathematical models behind the self-assembly were studied by many researches and a number of theoretical results were obtained. Here, we are going to present the concept of strong traces and a dynamic programming algorithm for their generation.

This is joint work with Drago Bokal, Tomaž Pisanski and Jernej Rus.

Properties of fullerenes are critically dependent on the distribution of their 12 pentagonal faces. It is well known that there are infinitely many IPR-fullerenes. IPR-fullerenes can be described as fullerenes in which each connected cluster of pentagons has size 1.

We studied the combinations of cluster sizes that can occur in fullerenes (and whether the clusters can be at an arbitrarily large distance from each other). For each possible partition of the number 12, we are able to decide whether the partition describes the sizes of pentagon clusters in a possible fullerene.

This is joint work with Gunnar Brinkmann, Patrick W. Fowler and Nico Van Cleemput.