## Algebraic Graph TheoryIn this substantial revision of a much-quoted monograph first published in 1974, Dr. Biggs aims to express properties of graphs in algebraic terms, then to deduce theorems about them. In the first section, he tackles the applications of linear algebra and matrix theory to the study of graphs; algebraic constructions such as adjacency matrix and the incidence matrix and their applications are discussed in depth. There follows an extensive account of the theory of chromatic polynomials, a subject that has strong links with the "interaction models" studied in theoretical physics, and the theory of knots. The last part deals with symmetry and regularity properties. Here there are important connections with other branches of algebraic combinatorics and group theory. The structure of the volume is unchanged, but the text has been clarified and the notation brought into line with current practice. A large number of "Additional Results" are included at the end of each chapter, thereby covering most of the major advances in the past twenty years. This new and enlarged edition will be essential reading for a wide range of mathematicians, computer scientists and theoretical physicists. |

### What people are saying - Write a review

User Review - Flag as inappropriate

hi

### Contents

Introduction | 1 |

Linear algebra in graph theory | 5 |

The spectrum of a graph | 7 |

Regular graphs and line graphs | 14 |

Cycles and cuts | 23 |

Spanning trees and associated structures | 31 |

The treenumber | 38 |

Determinant expansions | 44 |

Chromatic polynomials and spanning trees | 106 |

Symmetry and regularity | 113 |

Automorphisms of graphs | 115 |

Vertextransitive graphs | 122 |

Symmetric graphs | 130 |

Symmetric graphs of degree three | 138 |

The covering graph construction | 149 |

Distancetransitive graphs | 155 |

Vertexpartitions and the spectrum | 52 |

Colouring problems | 61 |

The chromatic polynomial | 63 |

Subgraph expansions | 73 |

The multiplicative expansion | 81 |

The induced subgraph expansion | 89 |

The Tutte polynomial | 97 |

Feasibility of intersection arrays | 164 |

Imprimitivity | 173 |

Minimal regular graphs with given girth | 180 |

191 | |

202 | |

### Other editions - View all

### Common terms and phrases

Additional Results adjacency algebra adjacency matrix adjacent vertices Aut(F automorphism group Ba(u Biggs bipartite graph block Cayley graph chapter characteristic polynomial chromatic number chromatic polynomial co-rank coefficients colour-partition colours complete graph components connected graph Consequently contains corresponding covering graph cubic graph cycle graph defined definition denote disjoint distance-regular graph distance-transitive graph edge of F edge-set eigenvalues eigenvector entries equation example expansion externally active finite formula function girth g given graph F graph of degree graph with degree graph with diameter incidence matrix induced subgraphs integer intersection array isomorphic Lemma Let F line graph Moore graph multiplicities natural number non-separable non-zero notation number of spanning number of vertices obtained pair partition permutation Petersen's graph properties Proposition quasi-separable rank polynomial regular graph satisfies spanning trees spectrum subgraphs of F subgroup subset Theorem tree-number Tutte polynomial vector vertex vertex-colouring vertex-set vertex-transitive graph vertices of F zero

### Popular passages

Page 198 - N. ROBERTSON, The smallest graph of girth 5 and valency 4, Bull. Amer. Math. Soc. 70 (1964), 824-825. 6. M. SPILL, "Ober minimale Graphen gegebener Taillenweite und Valenz,

Page 193 - PJ Cameron, CE Praeger, J. Saxl and GM Seitz, On the Sims' conjecture and distance-transitive graphs, Bull. London Math. Soc. 15 (1983), 499-506. A.