Molitierno Applications of Combinatorial Matrix Theory to Laplacian Matrices of Graphs

1. Auflage 2012
ISBN: 978-1-4398-6339-8
Verlag: Taylor & Francis
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 425 Seiten

Reihe: Discrete Mathematics and Its Applications

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.

Zielgruppe

Researchers and students in matrix graph theory, discrete mathematics, and computer science.

Autoren/Hrsg.

Molitierno, Jason J.

Fachgebiete

• Mathematik | Informatik Mathematik Mathematik Allgemein Diskrete Mathematik, Kombinatorik
• Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Algorithmen & Datenstrukturen
• Mathematik | Informatik Mathematik Operations Research Graphentheorie

Inhaltsverzeichnis

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

Graph Theory Preliminaries
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

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