You are previewing Topics in Graph Automorphisms and Reconstruction, Second Edition.
O'Reilly logo
Topics in Graph Automorphisms and Reconstruction, Second Edition

Book Description

This in-depth coverage of important areas of graph theory maintains a focus on symmetry properties of graphs. Standard topics on graph automorphisms are presented early on, while in later chapters more specialised topics are tackled, such as graphical regular representations and pseudosimilarity. The final four chapters are devoted to the reconstruction problem, and here special emphasis is given to those results that involve the symmetry of graphs, many of which are not to be found in other books. This second edition expands on several of the topics found in the first edition and includes both an enriched bibliography and a wide collection of exercises. Clearer proofs are provided, as are new examples of graphs with interesting symmetry properties. Any student who masters the contents of this book will be well prepared for current research in many aspects of the theory of graph automorphisms and the reconstruction problem.

Table of Contents

  1. Cover
  2. Halftitle page
  3. Title
  4. Copyright
  5. Dedication
  6. Contents
  7. Preface to the Second Edition
  8. Preface to the First Edition
  9. 1 Graphs and Groups: Preliminaries
    1. 1.1 Graphs and digraphs
    2. 1.2 Groups
    3. 1.3 Graphs and groups
    4. 1.4 Edge-automorphisms and line-graphs
    5. 1.5 A word on issues of computational complexity
    6. 1.6 Exercises
    7. 1.7 Notes and guide to references
  10. 2 Various Types of Graph Symmetry
    1. 2.1 Transitivity
    2. 2.2 Asymmetric graphs
    3. 2.3 Graph symmetries and the spectrum
    4. 2.4 Simple eigenvalues
    5. 2.5 Higher symmetry conditions
    6. 2.6 Exercises
    7. 2.7 Notes and guide to references
  11. 3 Cayley Graphs
    1. 3.1 Cayley colour graphs
    2. 3.2 Frucht’s and Bouwer’s Theorems
    3. 3.3 Cayley graphs and digraphs
    4. 3.4 The Doyle-Holt Graph
    5. 3.5 Non-Cayley vertex-transitive graphs
    6. 3.6 Coset graphs and Sabidussi’s Theorem
    7. 3.7 Double coset graphs and semisymmetric graphs
    8. 3.8 Hamiltonicity
    9. 3.9 Characters of abelian groups and Cayley graphs
    10. 3.10 Growth rates
    11. 3.11 Exercises
    12. 3.12 Notes and guide to references
  12. 4 Orbital Graphs and Strongly Regular Graphs
    1. 4.1 Definitions and basic properties
    2. 4.2 Rank 3 groups
    3. 4.3 Strongly regular graphs
    4. 4.4 The Integrality Condition
    5. 4.5 Moore graphs
    6. 4.6 Exercises
    7. 4.7 Notes and guide to references
  13. 5 Graphical Regular Representations and Pseudosimilarity
    1. 5.1 Elementary results
    2. 5.2 Abelian groups
    3. 5.3 Pseudosimilarity
    4. 5.4 Some basic results
    5. 5.5 Several pairs of pseudosimilar vertices
    6. 5.6 Several pairs of pseudosimilar edges
    7. 5.7 Large sets of mutually pseudosimilar vertices
    8. 5.8 Exercises
    9. 5.9 Notes and guide to references
  14. 6 Products of Graphs
    1. 6.1 General products of graphs
    2. 6.2 Direct product
    3. 6.3 Cartesian product
    4. 6.4 More products
    5. 6.5 Stability and two-fold automorphisms
    6. 6.6 Additional remarks on graph products
    7. 6.7 Exercises
    8. 6.8 Notes and guide to references
  15. 7 Special Classes of Vertex-Transitive Graphs and Digraphs
    1. 7.1 Generalised Petersen graphs
    2. 7.2 Kneser graphs and odd graphs
    3. 7.3 Metacirculant graphs
    4. 7.4 The quasi-Cayley graphs and digraphs
    5. 7.5 Generalised Cayley graphs
    6. 7.6 Exercises
    7. 7.7 Notes and guide to references
  16. 8 The Reconstruction Conjectures
    1. 8.1 Definitions
    2. 8.2 Some basic results
    3. 8.3 Maximal planar graphs
    4. 8.4 Digraphs and degree-associated reconstruction
    5. 8.5 Exercises
    6. 8.6 Notes and guide to references
  17. 9 Reconstructing from Subdecks
    1. 9.1 The endvertex-deck
    2. 9.2 Reconstruction numbers
    3. 9.3 The characteristic polynomial deck
    4. 9.4 Exercises
    5. 9.5 Notes and guide to references
  18. 10 Counting Arguments in Vertex-Reconstruction
    1. 10.1 Kocay’s Lemma
    2. 10.2 Counting spanning subgraphs
    3. 10.3 The characteristic and the chromatic polynomials
    4. 10.4 Exercises
    5. 10.5 Notes and guide to references
  19. 11 Counting Arguments in Edge-Reconstruction
    1. 11.1 Definitions and notation
    2. 11.2 Homomorphisms of structures
    3. 11.3 Lovász’ and Nash-Williams’ Theorems
    4. 11.4 Extensions
    5. 11.5 Exercises
    6. 11.6 Notes and guide to references
  20. References
  21. List of Notations
  22. Index of Terms and Definitions