Algebraic graph theory-Springer (2001).pdf

【实例简介】
Algebraic graph theory-Springer (2001) - (Graduate Texts in Mathematics) Chris Godsil, Gordon F. Royle.pdf
Chris Godsill Gordon Royle Department of Combinatorics Department of Computer Science and optimization University of Western Australia University of Waterloo Nedlands, Westem Australia 6907 Waterloo, Ontario N2L 3GI australia Canada gordon @cs. uwa.edu.au cgodsil @math. uwaterloo. ca Editorial board S. Axler F.W. Gehring K.A. Ribet Mathematics Department Mathematics Department Mathematics Department San francisco State East hall University of Califomia niversity University of Michigan at Berkeley San francisco, CA 94132 Ann Arbor, Mi 4810 Berkeley CA 94720-3840 JSA USA USA To Gillian and jane Mathematics Subject Classification(2000): OSCXX, O5EXX Library of Congress Cataloging-in-Publication Data Godsil, C D. Christopher David), 1949 Algebraic graph theory Chris Godsil, Gordon ROyle p cm. -( Graduate texts in mathematics; 207) Includes bibliographical references and inde ISBN 0-387-95241-l(hc: alk. paper) IsBN 0-387-95220-9(pbk. alk paper) I Graph theory I Royle, Gordon. I Title. Iu. series QA166G63200l 511,5-dc21 00-053776 Printed on acid-free paper. o 2001 Springer-Verlag New York, Inc. All rights reserved. This work may not be translated or copied in whole or in part without the written pemission of the publisher(Springer-Verlag New York, Inc, 175 Fifth Avenue, New York, NY 10010, USA), except for brief excerpts in connection with reviews or scholarly analysis, Use In connection with any form of information storage and retrieval, clectronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden the Trade Marks and Merchandise Marks Act, may accordingly be used freely by anyone sod e The use of general descriptive names, trade names, trademarks, etc, in this publication, even if the former are not especially identified, is not to be taken as a sign that such names, as under Production managed by A Orrantia; manufacturing supervised by Jerome Basma Electronically imposed from the authors' Post Script files Printed and bound by R.R. Donnelley and Sons, Harrisonburg, VA Printed in the united states of america 987654321 ISBN0387-95241-1 SPIN 10793786 (hardcover) IsBN0387-952209 SPIN 10791962 (softcover) Springer-Verlag New York Berlin Heidelberg A member of BertelsmannSpringer SciencetBusiness Media gmbH reface Many authors begin their preface by confidently describing how their book arose. We started this project so long ago, and our memories are so weak that we could not do this truthfully. Others begin by stating why they de- cided to write. Thanks to Freud, we know that unconscious reasons can be as important as conscious ones, and so this seems impossible too. More- over, the real question that should be addressed is why the reader should struggle with this text Even that question we cannot fully answer, so instead we offer an ex- planation for our own fascination with this subject. It offers the pleasure of seeing many unexpected and useful connections between two beautiful and apparently unrelated, parts of mathematics: algebra and graph theory At its lowest level, this is just the feeling of getting something for nothing After devoting much thought to a graph-theoretical problem, one suddenly realizes that the question is already answered by some lonely algebraic fact The canonical example is the use of eigenvalue techniques to prove that cer- tain extremal graphs cannot exist, and to constrain the parameters of those 0. Equally unexpected, and equally welcome, is the realization that some complicated algebraic task reduces to a question in graph theory for example, the classification of groups with bn pairs becomes the study of generaliz Although the subject goes back much further. Tutte's work was funda mental. His famous characterization of graphs with no perfect matchings was proved using Pfaffians; eventually, proofs were found that avoided any reference to algebra, but nonetheless, his original approach has proved fruit ful in modern work developing parallelizable algorithms for determining the viii Preface Preface maximun size of a matching in a graph. He showed that the order of the In the first part of the book we study the automorphisms and homomor vertex stabilizer of an arc-transitive cubic graph was at most 48. This is still hisms of graphs, particularly vertex-transitive graphs. We introduce the the most surprising result on the autmornorphism groups of graphs, and it necessary results on graphs and permutation groups, and take care to de- has stimulated a vast amount of work by group theorists interested in deriv- scribe a number of interesting classes of graphs: it seems silly, for example, ing analogous bounds for arc-transitive graphs with valency greater than to take the trouble to prove that a vertex transitive graph with valency k three. Tutte took the chromatic polynomial and gave us back the tutte has vertex connectivity at least 2(h+1/3 if the reader is not already in polynomial, an important generalization that we now find is related to the position to write down soine classes of vertex-transitive graphs. In addition surprising developments in knot theory connected to the Jones polynomial to results on the connectivity of vertex-transitive graphs we also present But Tutte's work is not the only significant source, Hoffman and sin- material on matchings and Hamilton cycles gleton's study of the maximal graphs with given valency and diameter led There are a number of well-known graphs with comparatively large au them to what they called Moore graphs. AIthough they were disappointed tomorphism groups that arise in a wide range of different settings-in in that despite the name, Moore graphs turned out to be very rare, this particular, the Petersen graph, the Coxeter graph, Tutte's 8-cage, and the was nonetheless the occasion for introducing eigenvalue techniques into the Hoffman-Singleton graph. We treat these famous graphs in some detail. We study of graph theory. also study graphs arising from projective planes and symplectic forms over oore graphs and generalized polygons led to the theory of distance 4-dimensional vector spaces. These are examples of generalized polygons, regular graphs, first thoroughly explored by Biggs and his collaborators which can be characterized as bipartite graphs with diameter d and girth Generalized polygons were introduced by Tits in the course of his funda 2d. Moore graphs can be defined to be graphs with diameter d and girth mental work on finite simple groups. The parameters of finite generalized 2d+1. It is natural to consider these two classes in the same place, and we polygons were determined in a famous paper by Fcit and Higman; this carl do so still be viewed as one of the key results in algebraic graph theory. Seidel also We complete the first part of the book with a treatment of graph homo played a major role. The details of this story are surprising: His work was morphisms. We discuss Hedetniemi's conjecture in some detail, and provide actually motivated by the study of geometric problems in general metric an extensive treatment of cores(graphs whose endomorphisms are all au- spaces. This led him to the study of equidistant sets of points in projective tomorphisms). We prove that the complement of a perfect graph is perfect space or, equivalently, the subject of equiangular lines. Extremal sets of offering a short algebraic argument due to GaspariaIl. We pay particu equiangular lines led in turn to regular two-graphs and strongly regular ar attention to the Kneser graphs, which enables us to treat fractional graphs. Interest in strongly regular graphs was further stimulated when chromatic number and the Erdos-Ko-Rado theorem We deternine the group theorists used them to construct new finite simple groups chromatic number of the Kneser graphs(using Borsuk's theorem We make some explanation of the philosophy that has governed our The second part of our book is concerned with matrix theory. Chapter 8 choice of material. Our main aim has been to present and illustrate the provides a course in linear algebra for graph theorists. This includes an main tools and ideas of algebraic graph theory, with an emphasis on cur- extensive and perhaps nonstandard, treatment of the rank of a matrix. Fol- rent rather than classical topics. We place a strong emphasis on concrete lowing this we give a thorough treatment of interlacing, which provides one examples, agreeing entirely with H, Luneburg s admonition that". the goal of the most powerful ways of using eigenvalues to obtain graph-theoretic of theory is the mastering of examples. We have made a considerable effort information We derive the standard bounds on the size of independent to keep our treatment self-contained sets, but also give bounds on the maximum number of vertices in a bi Our view of algebraic graph theory is inclusive; perhaps some readers partite induced subgraph, We apply interlacing to establish that certain will be surprised by the range of topics we have treated--fractional chro- carbon molecules, known as fullerenes, satisfy a stability criterion. we treat matic number, Voronoi polyhedra, a reasonably complete introduction to strongly regular graphs and two-graphs. The main novelty here is a careful matroids, graph drawing-to mention the most unlikely. We also find oc discussion of the relation between the eigenvalues of the subconstituents casion to discuss a large fraction of the topics discussed in standard graph of a strongly regular graph and those of the graph itself. We use this to theory texts(vertex and edge connectivity, Hamilton cycles, matchings study the strongly regular graphs arising as the point graphs of generalized and colouring problems, to mention some examples quadrangles, and characterize the generalized quadrangles with lines of size We turn to the more concrete task of discussing the contents of this thi book.To begin, a brief summary: automorphisms and homomorphisms, The least eigenvalue of the adjacency matrix of a line graph is at least the adjacency and Laplacian matrix, and the rank polynomial 2 We present the beautiful work of Cameron, Goethals, Shult, and Seidel characterizing the ohs with least eigenvalue at least -2. We follow the Pre crace Preface xi original proof, which reduces the problem to determining the generalized that no two such readers will be able to agree on where we have sinned the quadrangles with lines of size three and also reveals a surprising and close connection with the theory of root systems. Both authors are human, and therefore strongly driven by the desire to Finally we study the Laplacian matrix of a graph. We consider the re- edit, emend, and reorganize anyone else' s work. One effect of this is that lation between the second-largest eigenvalue of the Laplacian and various there are very few places in the text where either of us could, with an interesting graph parameters, such as edge-connectivity. We offer several real confidence or plausibility, blame the other for the unfortunate and viewpoints on the relation between the eigenvectors of a graph and various inevitable mistakes that remain. In this matter, as in others, our wives, ou natural graph embeddings. We give a reasonably complete treatment of the friends, and our students have made strenuous attempts to point out, anld cut and How spaces of a graph, using chip-firing games to provide a novel to eradicate, our deficiencies. Nonetheless, some will still show through, and approach to some aspects of this subject so we must now throw ourselves on our readers'mercy. We do intend as an The last three chapters are devoted to the connection between graph exercise in public self-fiagellation, to maintain a webpage listing corrections theory and knot theory. The most startling aspect of this is the connection athttp://quoLl.uwaterloo.ca/agt/ between the rank polynomial and the jones polynomial A number of people have read parts of various versions of this book For a graph theorist, the Jones polynomial is a specialization of a and offered useful comments and advice as a result. In particular it is straightforward generalization of the rank polynomial of a graph. The rank a pleasure to acknowledge the help of the following: Rob Beezer,An- polynomial is best understood in the context of matroid theory and conse- thony bonato, dom de caen Reinhard Diestel, Michael Doob, Jim Geelen quently our treatment of it covers a significant part of matroid theory. We Tommy Jensen, Bruce richter make a determined attempt to establish the importance of this polynomial We finish with a special offer of thanks to norman biggs, whose own Al- offering a fairly complete list of its remarkable applications in graph the- hebraic graph Theory is largely responsible for our interest in this subject ory(and coding theory ). We present a version of Tutte' s theory of rotors which allows us to construct nonisomorphic 3-connected graphs with the Chris Godsil aterloo same rank polynomial Gordon royle Perth After this work on the rank polynomial, it is not difficult to derive the Jones polynomial and show that it is a useful knot invariant. In the last chapter we treat more of the graph theory related to knot diagrams. We characterize gauss codes and show that certain knot theory operations are just topological manifestations of standard results from graph theory, in particular, the theory of circle graphs As already noted, our treatment is generally self-contained. We assume familiarity with permutations, subgroups, anld homomorphisms of gr We use the basics of the theory of symmetric matrices, but in this case we do offer a concise treatment of the machinery. We feel that much of the text is accessible to strong undergraduates. Our own experience is that we can cover about three pages of material per lecture. Thus there is enough here for a number of courses, and we feel this book could even be used for a first course in graph theory. o The exercises range widely in difficulty. Occasionally the notes to a apter provide a reference to a paper for a solution to an exercise; it is then usually fair to assume that the exercise is at the difficult end of the spectrum. The references at the end of each chapter are intended to provide contact with the relevant literature but they are not intended to be complete. It is more than likely that any readers familiar with algebraic graph theory will find their favourite topics slighted; our consolation is the hope Contents Preface i 1 Graphs 1.1 Grap 1.2 Subgraph 1.3 Aut hisr 14H chis 1.5 Circulant graphs 1.6 Johnson graphs 9 1.7 Line Graphs 10 1. 8 Planar graphs 12 16 References 2 Groups 2.1 Permutation groups 19 2.2 Counting 2.3 Asymmetric graphs 2.4 Orbits on pairs 25 2.5 Primitivity 27 2.6 Primitivity and Connectivity E 30 Note References 普鲁 32 XIV 8 Transitive Graphs 33 3.1 Vertex-Transitive Graphs 6. 4 The Map gl 33 3.2 Edge- Transitive Graphs 65 Counting ho ng 109 3.3Ed 6.6 Products and colourings 110 3.4V Connectivity 6.7 Uniquely Colourable Graph 39 3.5 Matchings 6.8 Foldings and Covers ,114 43 3.6 Hamilton Paths and Cycles 6.9 Cores with No Triangles 3.7 Cayley graphs 6.10 The And, 118 3. 8 Directed Cayley Graphs with No Hamilton Cycles 6. 11 Colouring Andrasfai Graphs 119 49 3.9 Retracts 6.12 A Characterizat 21 3.10 Transpositions 6.13 Vertex-T e Grap. 123 52 Exercises 6.14 Cores of Cubic Vertex-Transitive Graphs 54 Exercises Notes 56 Refe otes 32 57 References 133 4 Arc-Transitive Graphs 59 4.1 Arc-Transitive Graphs 7 Kneser Graphs 1:5 59 4. 2 Arc Graphs 7.1 Fractional Colourings and Cliques 135 4.3 Cubic Arc-Transitive Graphs 7.2 Fractional C 63 4.4 The Petersen Graph 7. 3 Fractional Chromatic Number 13′ 7.4 Homomorphisms and Fractional Colourings 138 45 Distancc-Transitive Graphs.·· 4.6 The Coxeter Graph 7.5 Duality 141 4.7 Tutte's 8-Cage 7.6 Imperfect Grap 142 71 7.7 Cyclic Interval Graphs 145 Exercises 74 7.8 Erdos-Ko-Rado 146 76 7.9H rphisms of Kneser Graph References 76 7.10 Induced Homomorphisms 5 Generalized Polygons and Moore Graphs 7.11 The Chromatic Number of the Kneser Graph 77 5.1 Incidence Graph 7.12 Gale's Theorem 78 152 5.2 Projective Planes 79 7. 13 Welzl's Theorem 153 5.3 A Family of Projective Planes 7. 14 The Cartesian Product 80 5.4 Generalized Quadrangles 81 7.15 Strong Products and Colourings 5.5 A Family of Generalized Quadrangles Exercises 83 56 Generalized Polygons 84 5.7 Two Generalized Hexagons References 160 5.8 Moore Graphs 90 8 Matrix Theory 163 5.9 The Hoffman-Singleton Graph 92 8.1 The Adjacency M 16 5.10 De 8.2 The Incidence Matrix 165 Exercises 97 8.3 The Incidence Matrix of an Oriented Graph 167 Notes .100 8. 4 Symmetric Matrices 169 References 8.5 Eigenvectors 171 6 Homomorphisms 8.6 Positive Serrnidefinite Matrices 6. 1 The Basic 103 8.7 Subharmonic Functions 175 103 6 Cores 8. 8 The Perron-Frobenius Theorem 178 104 63P 8.9 The Rank of a Symmetric Matrix 179 106 8.10 The Binary Rank of the Adjacency Matrix 181 xvi Contents Contents 8.11 The Symplectic Graph 8. 12 Spectral Decomposition 11. 8 The Two-Graph on 276 Vertices 260 Exercises 8.13 Rational Functions 262 Exercises,、,, 263 8 References.,、 Notes 192 References .192 12 Line Graphs and Eigenvalues 265 26 9 Interlacing 12.1 Generalized Line Graphs 198 12.2 Star-Closed Sets of Lines 9.1Ir 266 interlacing·· 193 12.3 Reflections 9.2 Inside and Outside the Petersen Graph 12.4 Inde ble Star-Closed Sets 9.3 Equitable Partitions 268 195 9. 4 Eigenvalues of Kneser graph 12.5 A Generating Sct 270 12.6 The Classification 9.5 More Interlacing 271 202 9.6 More Applications 12. 7 Root Systems 272 203 9.7 Bipartite Subgraphs 12.8 Consequences 274 206 9.8 Fullerenes 12.9 A Strongly Regular Grapl 276 208 Exercises 9.9 Stability of fulley 277 210 Exercises Notes 278 213 References notes 278 215 References..、,,, 6 13 The Laplacian of a Graph 279 10 Strongly Regular Graphs 13. 1 The Laplacian Matrix 279 217 132T 10.1 Parameters 218 13.3 Representations 10.2 Eigenvalues 284 219 13.4 Energy and Eigenvalues 287 10.3 Some Characterizations 221 10.4 Latin Square 13.5 Connectivit 288 Grap 2 13.6 Interlac 10.5 Small Strongly Regular Graphs g ..226 13.7 Conductance and Cutsets 292 L0.6 Local Eigenvalues 227 293 107 The Krein bounds.,,,、,.·,, 13.8 How to Draw a graph 231 10.8 Goneralized Quadrangles 13. 9 The Generalized Laplacian 295 235 10. 9 Lines of Size Three 13. 10 Multiplicities 298 237 10.10 Quasi-s 13. 11 Embeddings tric D ,300 1g 239 Exercis 302 10.11 The Witt Design on 23 Points 241 notes 10.12 The Symplectic Graphs 305 ,,,,242 References Exercises 306 244 .246 14 Cuts and flowg 307 Ref 247 14. 1 The Cut Space 308 11 Two-Graphs 14. 2 The Flow Space 310 249 11.1 Equiangular Lines 14.3 Planar Graphs 312 249 11.2 The absolute Bound 14.4 Bases and Ear Decompositions 313 251 14.5 Lattic 11.3 Tightness 315 252 11. 4 The Relative Bound 14.6 Duality 316 253 14.7 Integer Cuts and Flows 31 g 254 11.6 Regular Two-Graphs 14.8 Projections and Duals 319 256 11.7 Switching and Strongly Regular Graph 14. 9 Chip Firing 321 258 14.10 Two Bounds 323 lIt Content 14.11 Recurrent States 14.12 Critical States 325 17.3 Link Components and Bicycles ,400 14.13 The Critical Group 326 17. 4 Gauss Codes 403 14.14 Voronoi Polyhedra 327 17.5 Chords and Circles 405 14.15 Bicycles 329 17.6 Flipping Words 407 14 16 The Principal Tripartition 332 17 Characterizing Gauss Codos 408 Exercises 334 17.8 Bent Tours and Spanning Trees 410 Notos 17. 9 Bent Partitions and the Rank polyNomial 413 Re 17.10Maps,,, eferences 414 338 17. 11 Orientable Ma 417 15 The Rank Polynomial 17. 12 Seifert Circles 151 Rank Functions..· 341 419 15.2 Matroids 34l 17.13 Seifert Circles and Rank 420 E 15.3 Dualit 343 423 note 424 15.4 Restriction and Contraction 344 References ··· 425 15.5 Code 346 15.6 The Deletion-Contraction Algorithm 347 Glossary of Symbols 427 15.7 Bicycles in Bi 349 Index inary codes 433 15.8 Two Graph Polynomials 351 15.9 Rank Pol 35 1510 Evaluations of the Rank polynomial,·· 355 15.11 The Weight Enumerator of a Code 357 15. 12 Colourings and Codes 358 15 13 Signed Matroids 359 15.14 Rotors 15.15 Submodular Functions .363 Exercise 366 N 369 References 371 16 Knot 16.1 Knots and Their Projections 373 鲁希 16.2 Reidemeister Moves 374 16. 3 Signed Plane graphs 376 16.4 Reidemeis 379 n graph 16.5 Reidemeister lnvariant..,,.. 381 16.6 The Kauffman Bracket 383 16.7The Jones Polynomial 385 16. 8 Connectivity y I ses 391 References 392 392 I7Knots and Er ycles 17.1 Eulerian Partitions and Tours 395 17.2 The Medial Graph 395 【实例截图】
【核心代码】