Quantitative Graph Theory: Mathematical Foundations and Applications

Ever since Euler’s famous problem about bridges, mathematicians have studied various properties of graphs. Many of the most famous problems in this area belong to a subfield that is often called “structural graph theory” or “descriptive graph theory,” in which people look at questions such as how connected a graph is, how many colors one would need to color it, or even simply whether two graph descriptions are isomorphic. More recently, there has been quite a bit of interest in what is called “quantitative graph theory,” which prefers to ask questions about how similar two graphs are (rather than just whether they are the same) or which vertices in a graph are the most central, or things of that nature. The book under review collects a number of papers that introduce the readers to various measures that have been proposed to analyze such questions and that also discuss various applications of these measures.

The book opens with an article entitled “What is Quantitative Graph Theory” by the two editors (Matthias Dehmer and Frank Emmert-Streib) along with Veronika Kraus and Stefan Pickl. As its title suggests, it gives a very quick introduction to the field. For example, it introduces several metrics that one could use to define a distance between two graphs \(G\) and \(H\). One such measure was given by Sobik and defines \(d(G,H) = Max(n(G),n(H))-n(K)\) where \(n\) is a function giving the number of vertices of a graph, and \(K\) is the largest graph that is a subgraph of both \(G\) and \(H\). The authors claim that this is a well-defined metric that has many uses, but do not go into much more detail than that. In fact, their article does not spend much time motivating any definitions or giving applications, instead referring the reader to a very extensive bibliography on the field of quantitative graph theory — the 20 page article references 186 articles!

The other fifteen chapters in the collection do go into significantly more depth and motivation of their work — a full table of contents can be seen by clicking the tab above. The assembled group of 36 authors include mathematicians, computer scientists, sociologists, biologists, and chemists. As one would expect, the articles vary quite a bit in their level of mathematical depth. As with many such collections, the articles overlap in some strange ways and the different authors on occasion use different names for the same things, but there is quite a bit of interesting mathematics throughout the collection.

One example of a measure that shows up in a number of the articles is the Wiener Index of a graph, defined to be the sum over all pairs of vertices of the length of the (not necessarily unique) shortest path between the two vertices. This measure was introduced in the 1940s by the chemist Harry Wiener who used it to determine the boiling point of certain alkanes, but over the subsequent decades has found many applications in network analysis, crystallography, and cryptography, as well as other parts of chemistry. While the index is easy to define and straightforward to compute for small graphs, it is not hard to see that the naive approaches to compute it will get increasingly difficult as your graph has more and more vertices, and several of the papers in this volume (as well as many more elsewhere) look at ways to simplify the calculations under extra hypotheses on the graph.

While some of the papers in this collection look at the pure mathematics involved in quantitative graph theory and others tackle algorithmic questions, a number of the papers look explicitly at applications. For example, a paper by Philip Sinclair uses measures of betweenness and centrality to analyze political networks in Mexico to determine who the most influential politicians are. Another paper, by Martin Welk, uses graph indices to attempt to discern the texture of various three-dimensional objects from images of these objects. Other articles look at chemoinformatics and the complexity of chemical compounds.

The editors have done a nice job collecting articles that will be accessible to most graduate students in mathematics. This is not a textbook and, to truly learn the subject, I suspect one would want to look elsewhere. But these articles will give an interesting taste of some exciting mathematics and give the reader plenty of ideas of where to go to learn more. If nothing else, this collection will convince readers that graph theory, or at least large parts of it, belongs solidly under the category of applied mathematics, and that there is very interesting work being done in the area.

Darren Glass is an Associate Professor of Mathematics at Gettysburg College. His research interests are largely centered on Galois theory, Algebraic Geometry, and Cryptography, though he finds himself dabbling in Graph Theory more and more. He can be reached at dglass@gettysburg.edu.