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.

Table of Contents

1 Preliminaries

2 Incidence Matrix

3 Adjacency Matrix

4 Laplacian Matrix

5 Cycles and Cuts

6 Regular Graphs

7 Line Graph of a Tree

8 Algebraic Connectivity

9 Distance Matrix of a Tree

10 Resistance Distance

11 Laplacian Eigenvalues of Threshold Graphs

12 Positive Definite Completion Problem

13 Matrix Games Based on Graphs

Hints and Solutions to Selected Exercises

bout the Author

Ravindra B. Bapat had his schooling and undergraduate education in Mumbai. He obtained B.Sc. from University of Mumbai, M.Stat. from the Indian Statistical Institute, New Delhi and Ph.D. from the University of Illinois at Chicago in 1981.

After spending one year in Northern Illinois University in DeKalb, Illinois and two years in Department of Statistics, University of Mumbai, Prof. Bapat joined the Indian Statistical Institute, New Delhi, in 1983, where he holds the position of Professor, Stat-Math Unit, the moment. He held visiting positions at various Universities in the U.S. and visited several Institutes abroad in countries including France, Holland, Canada, China and Taiwan for collaborative research and seminars.

The main areas of research interest of Prof. Bapat are nonnegative matrices, matrix inequalities, matrices in graph theory and generalized inverses. He has published more than 100 research papers in these areas in reputed national and international journals and guided three Ph.D. students. He has written books on Linear Algebra, published by Hindustan Book Agency, Springer and Cambridge University Press. He wrote a book on Mathematics for the general reader, in Marathi, which won the state government award for best literature in Science for 2004.

Prof. Bapat has been on the editorial boards of Linear and Multilinear Algebra, Electronic Journal of Linear Algebra, India Journal of Pure and Applied Mathematics and Kerala Mathematical Association Bulletin. He has been elected Fellow of the Indian Academy of Sciences, Bangalore and Indian National Science Academy, Delhi.

Prof. Bapat served as President of the Indian Mathematical Society during its centennial year 2007-2008. For the past several years he has been actively involved with the Mathematics Olympiad Program in India and served as the National Coordinator for the Program. Prof. Bapat served as Head, ISI Delhi Centre, during 2007-2011. He was awarded the J.C. Bose fellowship in 2009.