1st Edition

Applications of Combinatorial Matrix Theory to Laplacian Matrices of Graphs

By Jason J. Molitierno Copyright 2012
    426 Pages 226 B/W Illustrations
    by Chapman & Hall

    On the surface, matrix theory and graph theory seem like very different branches of mathematics. However, adjacency, Laplacian, and incidence matrices are commonly used to represent graphs, and many properties of matrices can give us useful information about the structure of graphs.

    Applications of Combinatorial Matrix Theory to Laplacian Matrices of Graphs is a compilation of many of the exciting results concerning Laplacian matrices developed since the mid 1970s by well-known mathematicians such as Fallat, Fiedler, Grone, Kirkland, Merris, Mohar, Neumann, Shader, Sunder, and more. The text is complemented by many examples and detailed calculations, and sections followed by exercises to aid the reader in gaining a deeper understanding of the material. Although some exercises are routine, others require a more in-depth analysis of the theorems and ask the reader to prove those that go beyond what was presented in the section.

    Matrix-graph theory is a fascinating subject that ties together two seemingly unrelated branches of mathematics. Because it makes use of both the combinatorial properties and the numerical properties of a matrix, this area of mathematics is fertile ground for research at the undergraduate, graduate, and professional levels. This book can serve as exploratory literature for the undergraduate student who is just learning how to do mathematical research, a useful "start-up" book for the graduate student beginning research in matrix-graph theory, and a convenient reference for the more experienced researcher.

    Matrix Theory Preliminaries
    Vector Norms, Matrix Norms, and the Spectral Radius of a Matrix
    Location of Eigenvalues
    Perron-Frobenius Theory
    Doubly Stochastic Matrices
    Generalized Inverses

    Graph Theory Preliminaries
    Introduction to Graphs
    Operations of Graphs and Special Classes of Graphs
    Connectivity of Graphs
    Degree Sequences and Maximal Graphs
    Planar Graphs and Graphs of Higher Genus

    Introduction to Laplacian Matrices
    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
    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

    The Algebraic Connectivity
    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 Fiedler Vector and Bottleneck Matrices for Trees
    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

    Bottleneck Matrices for Graphs
    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

    The Group Inverse of the Laplacian Matrix
    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


    Jason J. Molitierno

    … 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). … 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, MAA Reviews, October 2012

    The book owes its textbook appeal to detailed proofs, a large number of fully elaborated examples and observations, and a handful of exercises, making beginning graduate students as well as advanced undergraduates its primary audience. Still, it can serve as useful reference book for experienced researchers as well.
    —Zentralblatt MATH