- Membership
- MAA Press
- Meetings
- Competitions
- Community
- Programs
- Students
- High School Teachers
- Faculty and Departments
- Underrepresented Groups
- MAA Awards
- MAA Grants

- News
- About MAA

Publisher:

Champman & Hall/CRC

Publication Date:

2012

Number of Pages:

405

Format:

Hardcover

Series:

Discrete Mathematics and Its Applications

Price:

89.95

ISBN:

9781439863374

Category:

Textbook

[Reviewed by , on ]

John T. Saccoman

10/2/2012

This book is part of the series “Discrete Mathematics and its Applications.” It continues the recent line of books that exploit the connections between the two seemingly disparate subjects of graph theory and matrix theory. While some of these books are more along the lines of graduate-level research monographs (such as *An Introduction to the Theory of Graph Spectra* by Cvetković, Rowlinson, and Simić), or an undergraduate textbook (*Graphs and Matrices *by Bapat) , this book works well as a reference textbook for undergraduates. Indeed, it is a distillation of a number of key results involving, specifically, the Laplacian matrix associated with a graph (which is sometimes called the “nodal admittance matrix” by electrical engineers).

Two other texts, one by Brualdi and Ryser from 1991 (*Combinatorial Matrix Theory*) and one by Brualdi and Cvetković from 2009 (*A Combinatorial Approach to Matrix Theory and Its Applications*) have similar titles, but are at a higher level. In the former, such topics as permanents and Latin Squares are given treatment, while the latter discusses canonical forms and applications to electrical engineering, chemistry and physics.

After two chapters covering the preliminaries in Matrix Theory and Graph Theory necessary for the sequel, Molitierno presents an Introduction to Laplacian Matrices, with a proof of the Kirchhoff Matrix-Tree Theorem via Cauchy-Binet. He discusses Laplacians of weighted graphs as well as unweighted ones, and bounds on the eigenvalue spectra of certain classes of graphs. In particular, Molitierno focuses on the second smallest eigenvalue of a graph’s Laplacian matrix, called the algebraic connectivity of the graph.

The important work of Grone and Merris is given a decent treatment, as is Fielder’s. In fact, it is Fiedler’s theorem on eigenvectors that leads to a particular type of matrix that dominates the last two chapters of the book, the so-called “bottleneck matrices.” These matrices are used to determine such graph properties as algebraic connectivity. Chapter 6 covers the bottleneck matrices for trees, while some general classes of non-tree graphs are covered in chapter 7.

Molitierno’s book represents a well-written source of background on this growing field. The sources are some of the seminal ones in the field, and the book is accessible to undergraduates.

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

**Matrix Theory Preliminaries**Vector Norms, Matrix Norms, and the Spectral Radius of a Matrix

Location of Eigenvalues

Perron-Frobenius Theory

M-Matrices

Doubly Stochastic Matrices

Generalized Inverses

Introduction to Graphs

Operations of Graphs and Special Classes of Graphs

Trees

Connectivity of Graphs

Degree Sequences and Maximal Graphs

Planar Graphs and Graphs of Higher Genus

Matrix Representations of Graphs

The Matrix Tree Theorem

The Continuous Version of the Laplacian

Graph Representations and Energy

Laplacian Matrices and Networks

The Spectra of Laplacian Matrices Under Certain Graph Operations

Upper Bounds on the Set of Laplacian Eigenvalues

The Distribution of Eigenvalues Less than One and Greater than One

The Grone-Merris Conjecture

Maximal (Threshold) Graphs and Integer Spectra

Graphs with Distinct Integer Spectra

Introduction to the Algebraic Connectivity of Graphs

The Algebraic Connectivity as a Function of Edge Weight

The Algebraic Connectivity with Regard to Distances and Diameters

The Algebraic Connectivity in Terms of Edge Density and the Isoperimetric Number

The Algebraic Connectivity of Planar Graphs

The Algebraic Connectivity as a Function Genus k where k is greater than 1

The Characteristic Valuation of Vertices

Bottleneck Matrices for Trees

Excursion: Nonisomorphic Branches in Type I Trees

Perturbation Results Applied to Extremizing the Algebraic Connectivity of Trees

Application: Joining Two Trees by an Edge of Infinite Weight

The Characteristic Elements of a Tree

The Spectral Radius of Submatrices of Laplacian Matrices for Trees

Constructing Bottleneck Matrices for Graphs

Perron Components of Graphs

Minimizing the Algebraic Connectivity of Graphs with Fixed Girth

Maximizing the Algebraic Connectivity of Unicyclic Graphs with Fixed Girth

Application: The Algebraic Connectivity and the Number of Cut Vertices

The Spectral Radius of Submatrices of Laplacian Matrices for Graphs

Constructing the Group Inverse for a Laplacian Matrix of a Weighted Tree

The Zenger Function as a Lower Bound on the Algebraic Connectivity

The Case of the Zenger Equalling the Algebraic Connectivity in Trees

Application: The Second Derivative of the Algebraic Connectivity as a Function of Edge Weight

- Log in to post comments