You are here

Graphs and Matrices

R. B. Bapat
Publication Date: 
Number of Pages: 
[Reviewed by
John T. Saccoman
, on

In the preface, the author (R. P. Bapat) distinguishes his work from existing works by Biggs and Godsil and Royle by saying that, while the others are in the realm of Algebraic Graph Theory, that his work could be termed “linear algebraic graph theory.” Another related book, An Introduction to Graph Spectra, by Cvetkovic, Rowlinson and Simic, presents modern advances in the field, but is intended for a higher-level audience than Bapat’s book. A student having completed introductory courses in Linear Algebra and Graph Theory should be able to understand and benefit from this text.

At the end of each of the twelve chapters there are a few exercises and a good number of references. The references are presented as a kind of bibliography. Most of the “usual suspects” for this field are present, including Binet-Cauchy, Kirchhoff, Perron-Frobenius, Moon, etc. It would be more helpful if they were referenced in the body of the chapters as well, but the bibliography is fairly representative of work in the field, save for no references to the extensive work of A.K. Kelmans in this area.

Chapter 10 discusses the Laplacian eigenvalues of threshold graphs; while Russell Merris’ work is referenced liberally, the formula of Hammer and Kelmans is not mentioned at all. However, Bapat does include an interesting proof of the derivation of the Laplacian eigenvalues of threshold graphs, given the degree sequence and certain majorization results.

Two application chapters are included. Chapter 9 covers the “resistance distance” between nodes of a network, while Chapter 12 discusses Matrix games based zero-sum games on graph matrices.

In sum, this text would be a fine resource for an advanced undergraduate or someone wishing to learn more about this synergistic field of study.

John T. Saccoman is Professor of Mathematics at Seton Hall University in South Orange, NJ.

Preliminaries.- Incidence matrix.- Adjacency matrix.- Laplacian matrix.- Cycles and cuts.- Regular graphs.- Algebraic connectivity.- Distance matrix of a tree.- Resistance distance.- Laplacian eigenvalues of threshold graphs.- Positive definite completion problem.- Matrix games based on graphs.- Hints and solutions.