Faculty of Mathematics, Physics
and Informatics
Comenius University Bratislava

Algebraic Graph Theory Seminar - Soňa Pavlíková (24.11.2017)

Friday 24.11.2017 at 13:30, Lecture room M/XI


22. 11. 2017 09.42 hod.
By: Martin Mačaj

Soňa Pavlíková:
Inverses of graphs


Abstract:
The inverse of a graph with a non-singular adjacency matrix is another graph (uniquely determined by the original one up to isomorphism) whose spectrum consists precisely of the reciprocals of the eigenvalues of the original graph, including multiplicities. The motivation for studying inverses of graphs comes from lack of suitable bounds for the smallest non-negative eigenvalue of a graph, in contrast with a relative abundance of bounds for the largest eigenvalue. This principle has been used in applications related to quantum chemistry.

In the first part of talk we will deal with simple labeled graphs with non zero labels in a ring. If the adjacency matrix of such a graph is invertible, the inverse is an adjacency matrix of another graph, called the inverse of the original graph. If the ring is ordered, then balanced inverses - those with a positive product of labels along every cycle - are of interest. We introduce the concept of a derived labeled graph and show how it can be embedded into an inverse. We also prove a new result on balanced inverses of labeled trees and present a construction of new labeled graphs with balanced inverses from old.

In the second part we will investigate the so-called positively and negatively invertible graphs. The class of negatively invertible graphs turns out to contain models of important organic molecules and invertibility allows to derive bounds on the binding energy of such molecules. We will present a fairly general construction of new invertible graphs based on `bridging' a pair of invertible graphs, which, informally, means `joining' the pair by a new bipartite graph attached to the two graphs at suitable subsets of vertices.