Matrices in combinatorics and graph theory

✍ Scribed by Liu B., Lai H.-J.

• Publisher: Kluwer
• Year: 2000
• Tongue: English
• Leaves: 316
• Series: Network Theory and Applications Volume 3
• Category: Library

✦ Synopsis

The first chapter of this book provides a brief treatment of the basics of the subject. The other chapters deal with the various decompositions of non-negative matrices, Birkhoff type theorems, the study of the powers of non-negative matrices, applications of matrix methods to other combinatorial problems, and applications of combinatorial methods to matrix problems and linear algebra problems. The coverage of prerequisites has been kept to a minimum. Nevertheless, the book is basically self-contained (an Appendix provides the necessary background in linear algebra, graph theory and combinatorics). There are many exercises, all of which are accompanied by sketched solutions. Audience: The book is suitable for a graduate course as well as being an excellent reference and a valuable resource for mathematicians working in the area of combinatorial matrix theory.

✦ Table of Contents

Cover......Page 1
Matrices in Combinatorics and Graph Theory......Page 3
Contents......Page 5
Foreword......Page 8
Preface......Page 9
1.1 The Basics......Page 10
1.2 The Spectrum of a Graph......Page 14
1.3 Estimating the Eigenvalues of a Graph......Page 21
1.4 Line Graphs and Total Graphs......Page 26
1.5 Cospectral Graphs......Page 29
1.6 Spectral Radius......Page 33
1.7 Exercises......Page 47
1.8 Hints for Exercises......Page 50
2 Combinatorial Properties of Matrices......Page 56
2.1 Irreducible and Folly Indecomposable Matrices......Page 57
2.2 Standard Forms......Page 59
2.3 Nearly Reducible Matrices......Page 63
2.4 Nearly Decomposable Matrices......Page 67
2.5 Permanent......Page 70
2.6 The Class U(r,s)......Page 80
2.7 Stochastic Matrices and Doubly Stochastic Matrices......Page 86
2.8 Birkhoff Type Theorems......Page 90
2.9 Exercise......Page 99
2.10 Hints for Exercises......Page 101
3.1 The Frobenius Diophantine Problem......Page 106
3.2 The Period and The Index of a Boolean Matrix......Page 110
3.3 The Primitive Exponent......Page 116
3.4 The Index of Convergence of Irreducible Nonprimitive Matrices......Page 123
3.5 The Index of Convergence of Reducible Nonprimitive Matrices......Page 129
3.6 Index of Density......Page 134
3.7 Generalized Exponents of Primitive Matrices......Page 138
3.8 Fully indecomposable exponents and Hall exponents......Page 145
3.9 Primitive exponent and other parameters......Page 155
3.10 Exercises......Page 159
3.11 Hint for Exercises......Page 162
4.1 Matrix Solutions for Difference Equations......Page 169
4.2 Matrices in Some Combinatorial Configurations......Page 174
4.3 Decomposition of Graphs......Page 179
4.4 Matrix-Tree Theorems......Page 184
4.5 Shannon Capacity......Page 188
4.6 Strongly Regular Graphs......Page 198
4.7 Eulerian Problems......Page 204
4:8 The Chromatic Number......Page 212
4.9 Exercises......Page 218
4.10 Hints for Exercises......Page 220
5.1 Combinatorial Representation of Matrices and Determinants......Page 225
5.2 Combinatorial Proofs in Linear Algebra......Page 229
5.3 Generalized Inverse of a Boolean Matrix......Page 232
5.4 Maximum Determinant of a (0,1) Matrix......Page 238
5.5 Rearrangement of (0,1) Matrices......Page 244
5.6 Perfect Elimination Scheme......Page 253
5.7 Completions of Partial Hermitian Matrices......Page 257
5.8 Estimation of the Eigenvalues of a Matrix......Page 261
5.9 M-matrices......Page 269
5.10 Exercises......Page 279
5.11 Hints for Exercises......Page 280
6.1 Linear Algebra and Matrices......Page 283
6.2 The Term Rank and the Line Rank of a Matrix......Page 285
6.3 Graph Theory......Page 287
Index......Page 290
Bibliography......Page 297