On the spectra and walks of molecular and controllable graphs

Abstract

Walks in a graph G relate to its configuration and to the eigenspaces of its adjacency matrix G. In this thesis, we extend the notion of walks. It impacts on the inverse of G, settling a conjecture on the conductivity properties of molecules modelled by chemical graphs, whose vertices represent carbon atoms having degree at most three. Walks also bring out structural properties of a controllable system represented by G. The product of the weights of the edges in a walk of length on a weighted looped graph G is called the walk weight. We deduce closed form expressions for the generating function of the sum of walk weights of G between vertices among two subsets of the vertices of G. We produce three expressions for this generating function: one in terms of the eigenvalues and eigenspaces of G, one in terms of the inverse of the matrix, where I is the identity matrix, and one in terms of the characteristic polynomials of G and those of related graphs, called overgraphs, obtained from G by adding a vertex. In the latter case, characteristic polynomials with a reversal of their coefficients, called reverse polynomials, are employed. We introduce the notion of a walk of negative length on the graph G as being a walk on the weighted looped graph whose adjacency matrix is the inverse of that of G. Similar to the case for the usual, positively{long walks, we provide generating functions producing sums of walk weights of negative length, and relate these walk weight sums with those of positive length. Remarkably, if we use characteristic polynomials to produce generating functions of the sum of the weights of walks of negative lengths, the usual characteristic polynomials are used, rather than their reversal as in the case for positively long walks. In the literature, the walk matrix of a graph G is a square matrix whose ijth entry is the number of walks of length between vertex j and any other vertex of G. We extend this notion to walk matrices whose entries represent walks between each vertex and a subset of the vertex set of G. Hankel matrices whose entries enumerate walk weights of a graph are also discussed. They turn out to be Gram matrices of the columns of the walk matrix of the graph. Another matrix in the form of a Toeplitz matrix, combining walks of both positive and negative length, is also introduced. A new walk matrix that mimics the properties of the commonly used walk matrix, but containing the sum of walk weights of closed walks in G instead of the number of walks, is also proposed. Our study of properties revealed in walk matrices contributes to new discoveries in molecular chemistry and in control theory.