## Graphs and MatricesGraphs and Matrices provides a welcome addition to the rapidly expanding selection of literature in this field. As the title suggests, the book’s primary focus is graph theory, with an emphasis on topics relating to linear algebra and matrix theory. Information is presented at a relatively elementary level with the view of leading the student into further research. In the first part of the book matrix preliminaries are discussed and the basic properties of graph-associated matrices highlighted. Further topics include those of graph theory such as regular graphs and algebraic connectivity, Laplacian eigenvalues of threshold graphs, positive definite completion problem and graph-based matrix games. Whilst this book will be invaluable to researchers in graph theory, it may also be of benefit to a wider, cross-disciplinary readership. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

1 | |

12 Eigenvalues of symmetric matrices | 5 |

13 Generalized inverses | 7 |

14 Graphs | 9 |

Incidence Matrix | 11 |

21 Rank | 12 |

22 Minors | 13 |

23 Path matrix | 15 |

64 Strongly regular graphs and friendship theorem | 73 |

65 Graphs with maximum energy | 76 |

Algebraic Connectivity | 81 |

72 Classification of trees | 83 |

73 Monotonicity properties of Fiedler vector | 88 |

74 Bounds for algebraic connectivity | 89 |

Distance Matrix of a Tree | 95 |

81 Distance matrix of a graph | 96 |

24 Integer generalized inverses | 16 |

25 MoorePenrose inverse | 17 |

26 01 Incidence matrix | 19 |

27 Matchings in bipartite graphs | 21 |

Adjacency Matrix | 25 |

31 Eigenvalues of some graphs | 26 |

32 Determinant | 28 |

33 Bounds | 31 |

34 Energy of a graph | 36 |

35 Antiadjacency matrix of a directed graph | 37 |

36 Nonsingular trees | 39 |

Laplacian Matrix | 45 |

41 Basic properties | 46 |

42 Computing Laplacian eigenvalues | 47 |

43 Matrixtree theorem | 48 |

44 Bounds for Laplacian spectral radius | 50 |

45 EdgeLaplacian of a tree | 51 |

Cycles and Cuts | 57 |

52 Fundamental matrices | 59 |

53 Minors | 60 |

Regular Graphs | 65 |

62 Adjacency algebra of a regular graph | 70 |

82 Distance matrix and Laplacian of a tree | 99 |

83 Eigenvalues of the distance matrix of a tree | 104 |

Resistance Distance | 111 |

91 The triangle inequality | 112 |

92 Network ﬂows | 113 |

93 A random walk on graphs | 116 |

94 Effective resistance in electrical networks | 118 |

95 Resistance matrix | 119 |

Laplacian Eigenvalues of Threshold Graphs | 125 |

102 Threshold graphs | 129 |

103 Spectral integral variation | 131 |

Positive Deﬁnite Completion Problem | 137 |

112 Chordal graphs | 138 |

113 Positive definite completion | 140 |

Matrix Games Based on Graphs | 145 |

122 Vertex selection games | 147 |

123 Tournament games | 148 |

124 Incidence matrix games | 151 |

Hints and Solutions to Selected Exercises | 159 |

165 | |

169 | |

### Other editions - View all

### Common terms and phrases

adjacency matrix algebraic connectivity algebraic multiplicity assume bipartite graph characteristic polynomial characteristic vertex Chordal graphs cofactor cograph column sums completes the proof connected graph Corollary denote directed graph distance matrix edges of G eigenvalues of L(G eigenvector equals the number Fiedler vector fundamental cycle G G G G is connected g-inverse graph G graph with V(G hence i,j)-element incidence matrix indexed by V(G integer Laplacian integral Laplacian of G Lemma Let G let Q linearly independent matrix game matrix of G n×n matrix nonnegative nonzero Note number of edges number of spanning number of vertices optimal strategies orthogonal partial positive definite partitioned path positive definite completable principal minors principal submatrix proof is complete prove pure strategy rank resistance distance respectively row and column Show spanning tree specification graph strongly regular graph submatrix symmetric matrix Theorem threshold graph tree of G tree with V(T vertex selection game vertex set