Graphs and Matrices (Universitext)

This New Edition Illustrates The Power Of Linear Algebra In The Study Of Graphs. The Emphasis On Matrix Techniques Is Greater Than In Other Texts On Algebraic Graph Theory. Important Matrices Associated With Graphs (for Example, Incidence, Adjacency And Laplacian Matrices) Are Treated In Detail. Presenting A Useful Overview Of Selected Topics In Algebraic Graph Theory, Early Chapters Of The Text Focus On Regular Graphs, Algebraic Connectivity, The Distance Matrix Of A Tree, And Its Generalized Version For Arbitrary Graphs, Known As The Resistance Matrix. Coverage Of Later Topics Include Laplacian Eigenvalues Of Threshold Graphs, The Positive Definite Completion Problem And Matrix Games Based On A Graph. Such An Extensive Coverage Of The Subject Area Provides A Welcome Prompt For Further Exploration. The Inclusion Of Exercises Enables Practical Learning Throughout The Book. In The New Edition, A New Chapter Is Added On The Line Graph Of A Tree, While Some Results In Chapter 6 On Perron-frobenius Theory Are Reorganized. Whilst This Book Will Be Invaluable To Students And Researchers In Graph Theory And Combinatorial Matrix Theory, It Will Also Benefit Readers In The Sciences And Engineering. Preliminaries -- Incidence Matrix -- Adjacency Matrix -- Laplacian Matrix -- Cycles And Cuts -- Regular Graphs -- Line Graph Of A Tree -- Algebraic Connectivity -- Distance Matrix Of A Tree -- Resistance Distance -- Laplacian Eigenvalues Of Threshold Graphs -- Positive Definite Completion Problem -- Matrix Games Based On Graphs. By Ravindra B. Bapat. Preface......Page 6 About the Second Edition......Page 8 Contents......Page 9 1.1 Matrices......Page 12 1.2 Eigenvalues of Symmetric Matrices......Page 16 1.3 Generalized Inverses......Page 19 1.4 Graphs......Page 21 References and Further Reading......Page 22 2 Incidence Matrix......Page 23 2.1 Rank......Page 24 2.2 Minors......Page 25 2.3 Path Matrix......Page 27 2.4 Integer Generalized Inverses......Page 28 2.5 Moore--Penrose Inverse......Page 30 2.6 0--1 Incidence Matrix......Page 32 2.7 Matchings in Bipartite Graphs......Page 33 References and Further Reading......Page 35 3 Adjacency Matrix......Page 37 3.1 Eigenvalues of Some Graphs......Page 38 3.2 Determinant......Page 40 3.3 Bounds......Page 43 3.4 Energy of a Graph......Page 48 3.5 Antiadjacency Matrix of a Directed Graph......Page 50 3.6 Nonsingular Trees......Page 52 References and Further Readings......Page 58 4 Laplacian Matrix......Page 59 4.1 Basic Properties......Page 60 4.2 Computing Laplacian Eigenvalues......Page 61 4.3 Matrix-Tree Theorem......Page 62 4.4 Bounds for Laplacian Spectral Radius......Page 64 4.5 Edge-Laplacian of a Tree......Page 65 References and Further Reading......Page 69 5.1 Fundamental Cycles and Fundamental Cuts......Page 70 5.2 Fundamental Matrices......Page 72 5.3 Minors......Page 73 References and Further Reading......Page 77 6.1 Perron--Frobenius Theory......Page 78 6.2 Adjacency Algebra of a Regular Graph......Page 83 6.3 Complement and Line Graph of a Regular Graph......Page 84 6.4 Strongly Regular Graphs and Friendship Theorem......Page 87 6.5 Graphs with Maximum Energy......Page 90 References and Further Reading......Page 94 7.1 Block Graphs......Page 95 7.2 Signless Laplacian Matrix......Page 101 7.3 Nullity of the Line Graph of a Tree......Page 103 References and Further Reading......Page 107 8.1 Preliminary Results......Page 108 8.2 Classification of Trees......Page 110 8.3 Monotonicity Properties of Fiedler Vector......Page 115 8.4 Bounds for Algebraic Connectivity......Page 117 Refrences and Further Reading......Page 121 9 Distance Matrix of a Tree......Page 122 9.1 Distance Matrix of a Graph......Page 124 9.2 Distance Matrix and Laplacian of a Tree......Page 127 9.3 Eigenvalues of the Distance Matrix of a Tree......Page 132 References and Further Reading......Page 137 10 Resistance Distance......Page 138 10.1 The Triangle Inequality......Page 139 10.2 Network Flows......Page 141 10.3 A Random Walk on Graphs......Page 144 10.4 Effective Resistance in Electrical Networks......Page 145 10.5 Resistance Matrix......Page 146 References and Further Reading......Page 151 11.1 Majorization......Page 152 11.2 Threshold Graphs......Page 156 11.3 Spectral Integral Variation......Page 158 References and Further Reading......Page 162 12.1 Nonsingular Completion......Page 163 12.2 Chordal Graphs......Page 164 12.3 Positive Definite Completion......Page 166 References and Further Reading......Page 170 13.1 Matrix Games......Page 171 13.2 Vertex Selection Games......Page 173 13.3 Tournament Games......Page 175 13.4 Incidence Matrix Games......Page 177 References and Further Reading......Page 183 Chapter 2......Page 184 Chapter 5......Page 185 Chapter 7......Page 186 Chapter 8......Page 187 Chapter 11......Page 188 Chapter 12......Page 189 Chapter 13......Page 190 Bibliography......Page 191 Index......Page 195 "This new edition illustrates the power of linear algebra in the study of graphs. The emphasis on matrix techniques is greater than in other texts on algebraic graph theory. Important matrices associated with graphs (for example, incidence, adjacency and Laplacian matrices) are treated in detail. Presenting a useful overview of selected topics in algebraic graph theory, early chapters of the text focus on regular graphs, algebraic connectivity, the distance matrix of a tree, and its generalized version for arbitrary graphs, known as the resistance matrix. Coverage of later topics include Laplacian eigenvalues of threshold graphs, the positive definite completion problem and matrix games based on a graph. Such an extensive coverage of the subject area provides a welcome prompt for further exploration. The inclusion of exercises enables practical learning throughout the book. In the new edition, a new chapter is added on the line graph of a tree, while some results in Chapter 6 on Perron-Frobenius theory are reorganized. Whilst this book will be invaluable to students and researchers in graph theory and combinatorial matrix theory, it will also benefit readers in the sciences and engineering."--Publisher's website