Algebraic Graph Theory

【实例简介】
Algebraic Graph Theory
NORMAN BIGGS Lecturer in mathematics Royal Holloway College, University of london Algebraic graph Theory CAMBRIDGE UNIVERSITY PRESS Published by the Syndics of the Cambridge University Press Bentley House, 200 Euston Road, London Nw1 2DB American Branch: 32 East 57th Street, New York. N.Y. 10022 C Cambridge University Press 1974 Library of Congress Catalogue Card Number: 73-86042 ISBN:052120335X First published 1974 Printed in Great Britain at the University Printing House, Cambridge (Brooke Crutchley, University Printer) Contents Preface page vll 1 Introduction PART ONE- LINEAR ALGEBRA IN GRAPH THEORY 2 The spectrum of a graph 9 3 Regular graphs and line graphs 14 4 The homology of graphs 5 spanning trees and associated structures 29 6 Complexity 34 7 Determinant expansions 40 PART TWO-COLOURING PROBLEMS 8 Vertex-colourings and the spectrum 9 The chromatic polynomial 10 Edge-subgraph expansions 64 11 The logarithmic transformation 72 12 The vertex-subgraph expansion 78 13 The Tutte polynomial 86 14 The chromatic polynomial and spanning trees 94 PART THREE-SYMMETRY AND REGULARITY OF GRAPHS 15 General properties of graph automorphisms 101 16 Vertex-transitive graphs 106 17 Symmetric graphs 112 Contents 18 Trivalent symmetric graphs 9e119 19 The covering-graph construction 127 20 Distance-transitive graphs 132 21 The feasibility of intersection arrays 140 22 Primitivity and imprimitivity 147 23 Minimal regular graphs with given girth 154 Bibliography 165 ndeⅹ 169 reface t is a pleasure for me to acknowledge the help which I have received during the preparation of this book. A preliminary draft of the manuscript was read by Dr R.J. Wilson, and his detailed comments resulted in substantial changes and improve ments. I was then fortunate to be able to rely upon the expert assistance of my wife for the production of a typescript. Ideas and helpful criticisms were offered by several friends and col leagues, among them G. de Barra, R. M. Damerell, A D Gardiner,Iv K. Guy, P. McMullen and J. W. Moon. The general editor of the Cambridge Mathematical tracts, Professor C.T. C Wall, was swift and perceptive in his appraisal, and his com ments were much appreciated. The staff of the Cambridge University Press maintained their usual high standard of courtesy and efficiency throughout the process of publication during the months January-April 1973, when the final stages of the writing were completed, I held a visiting appointment at the University of Waterloo, and my thanks are due to Professor W.T. Tutte for arranging this. In addition, I owe a mathe matical debt to Professor Tutte, for he is the author of the two results, Theorems 13.9 and 18.6, which I regard as the most important in the book. i should venture the opinion that, were it not for his pioneering work, these results would still be unknown to this day NORMAN BIGGS Waterloo, Canada March 1973 l。 Introduction This book is concerned with the use of algebraic techniques in the study of graphs. We aim to translate properties of graphs into algebraic properties and then, using the results and methods of algebra, to deduce theorems about graphs The exposition which we shall give is not part of the modern functorial approach to topology, despite the claims of those who hold that, since graphs are one-dimensional spaces, graph theory is merely one-dimensional topology. By that definition, algebraic graph theory would consist only of the homology of 1-complexes But the problems dealt with in graph theory are more delicate than those which form the substance of algebraic topology, and even if these problems can be generalized to dimensions greater than one, there is usually no hope of a general solution at the present time. Consequently, the algebra used in algebraic graph theory is largely unrelated to the subject which has come to be known as homological algebra This book is not an introduction to graph theory It would be to the reader's advantage if he were familiar with the basic con cepts of the subject, for example, as they are set out in the book by R.J. Wilson entitled Introduction to graph theory. However for the convenience of those readers who do not have this back ground, we give brief explanations of important standard terms These explanations are usually accompanied by a reference to Wilson's book(in the form [W, p. 99]), where further details may be found. In the same way, some concepts from permutation- group theory are accompanied by a reference [B, p. 99] to the author's book Finite groups of automorphisms. Both these books are described fully at the end of this chapter a few other books are also referred to for results which may be unfamiliar to some readers. In such cases, the result required is necessary for an understanding of the topic under discussion, so that the reference is given in full, enclosed in square brackets Introduction where it is needed. Other references, of a supplementary nature are given in parentheses in the form(Smith 1971)or Smith(1971) In such cases, the full reference may be found in the bibliography at the end of the book The tract is in three parts, each of which is further subdivided into a number of short chapters. Within each chapter, the major definitions and results are labelled using the decimal system The first part deals with the applications of linear algebra and matrix theory to the study of graphs. We begin by introducing the adjacency matrix of a graph; this matrix completely deter- mines the graph, and its spectral properties are shown to be related to properties of the graph. For example, if a graph is regular, then the eigenvalues ofits adjacency matrix are bounded in absolute value by the valency of the graph. In the case of a line graph, there is a strong lower bound for the eigenvalues Another matrix which completely describes a graph is the incidence matrix of the graph. This matrix represents a linear mapping which, in modern language, determines the homology of the graph; however, the sophistication of this language obscures the underlying simplicity of the situation. The problem of choosing a basis for the homology of a graph is just that of finding a fundamental system of circuits, and we solve this problem by using a spanning tree in the graph. At the same time we study the cutsets of the graph. These ideas are then applied to the systematic solution of network equations, a topic which supplied the stimulus for the original theoretical development We then investigate various formulae for the number of span ning trees in a graph, and apply these formulae to several well known families of graphs. The first part of the book ends with results which are derived from the expansion of certain deter minants, and which illuminate the relationship between a graph and the characteristic polynomial of its adjacency matrix The second part of the book deals with the problem of colouring the vertices of a graph in such a way that adjacent vertices have different colours. The least number of colours for which such a colouring is possible is called the chromatic number of the graph and we begin by investigating some connections between this 【实例截图】
【核心代码】