Introduction to Chemical Graph Theory
The representation of an atomic structure by a graph where the vertices represent atoms and the edges the bondings, is an important application of (connected undirected) graphs, studied in a field called chemical graph theory. The overall (topological) structure of such a graph can be caught into just one number called a chemical index and they are often related to chemical properties (like boiling point or energy). Especially the maximum or minimum values of such an index for a given graph topology are particularly important.
Many of these chemical indices have been proposed. They are often defined in terms of (topological) distances between the vertices, vertex degrees, or on the spectra of matrices describing the graph (like the adjacency matrix or the Laplacian) as in spectral graph theory. This book studies some of the most important of these indices. Although a previous course on graph theory is not really necessary (the main concepts and definitions are recalled in the beginning) it might help if the reader is somewhat familiar with the terminology. So after a brief introduction, the four other chapters are an in-depth discussion of the Wiener index, the Radić index, the dual Merrifield-Simmons and Hosoya indices, and several spectral indices.
The approach is systematic and theoretical with many definitions and proofs of lemmas, propositions and theorems. The indices are studied for general graphs as well as for particular graph structures such as trees, stars, or caterpillars so that exact values or bounds for maxima and minima can be derived. Trees are the main ingredient and they have a prominent role throughout the book. Each chapter has a list of exercises appended that are usually asking to prove a result in some special case or to prove a property of the chapter whose proof has been skipped. Although it is all about applications in chemistry, the chemical interpretation of all these properties is not worked out and in the best case only briefly mentioned. It is a nice feature though that the chapters start with some overview of what is to follow before one gets lost in the technical details. The practical implementation of how all these indices should be computed or the complexity estimates of the algorithms that should be used are not the main concerns of the authors (at least not in this book). This computational aspect should however not be underestimated because some of these problems are of combinatorial nature and computing can become an issue for large general non-planar graphs representing crystal structures, but this is not an application that the authors have in mind here. Clearly special procedures can be used for special structures that reduce the computing time.
The Wiener index is the most classic of all these indices. Proposed in 1947 by Harry Wiener (the chemist, not Norbert Wiener the mathematician). It can be defined as the sum of the distances between any couple of vertices of the graph. It is obviously an integer. Its properties are mainly studied here on trees and caterpillars and other special cases. Both the properties of the Wiener index for a certain structure, and the inverse problem of checking the existence of a structure having a given Wiener index are discussed.
The Radić index (1975) is based on vertex degrees. Classically it is the sum over all edges of the inverses of the geometric means of the degrees of the two endpoints but several variations are possible. More generally the indices are the sum over all edges uv of a function f(u,v) which depends on the degrees of the vertices u and v. Hence several other indices based on vertex degrees with different levels of complexity are also discussed (Zagreb, connectivity, ABC).
A subset of vertices in which no couple is connected by an edge is an independent set. Its dual is called a matching, that is a subset of edges without a common vertex. The independence and matching number of a graph are defined as the corresponding maxima. The Merrifield-Simmons index (1980) counts the number of independent sets and the Hosoya index (1971) the number of matchings. Clearly both have again integer values. Fibonacci numbers appear naturally as extreme values obtained for a path.
Finally the classical 0-1 adjacency matrix and its dual, the incidence matrix, are introduced. Even more interesting is the Laplacian (and signless Laplacian), which consist of the diagonal matrix of the vertex degrees minus (respectively plus) the adjacency matrix. Since these matrices are symmetric, their spectra are real. This is a property from linear algebra not proved here. This chapter certainly requires more mathematics outside of combinatorial calculus in the sense that one needs several other properties from linear algebra too and for example trigonometric polynomials are employed to describe the spectra. This expects that the reader has some knowledge about these domains. On the other hand, this spectral analysis gives much more possibilities to analyse the properties of the graph than the indices of the previous chapters. But there are also some surprising relations. For example, for a graph with n vertices, 1/n times the sum of the inverses of the nonzero eigenvalues of the Laplacian is known as the Kirchoff index. For a tree, it is equal to the Wiener index.
The energy of a graph is the sum of the absolute values of the eigenvalues of the adjacency matrix. Explicit expressions are computed for special graphs, but in general nontrivial integral representations are obtained. An energy index can also be defined based on eigenvalues of the Laplacian matrix and several variants are possible. For example the spectral radius can be used as an invariant, or the Estrada index (2000) which is the sum of the exponentials of the eigenvalues.
Although the main interest of the text is to introduce all these definitions and properties for applications in molecular chemistry, some of these, especially the spectral and energy indices, have also applications in other domains such as networks. The treatment is however focussing on the theory and the mathematics. The applications as well as the numerical or algorithmic computations are not included. The book is introductory in the sense that only the main indices are discussed and is restricted to planar graphs, but what is included is worked out in detail. It can be used for a course in mathematical chemistry, or it can be used for self study.