Topics in Graph Automorphisms and Reconstruction

by Josef Lauri , Raffaele Scapellato

• ISBN13: 9780521529037
• ISBN10: 0521529034
• Format: Paperback
• Copyright: 2003-03-17
• Publisher: Cambridge University Press

Summary

The aim of this book is to provide in depth coverage of selected areas of graph theory, and throughout the focus is mainly 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 four final chapters are devoted to the reconstruction problem, and here greater emphasis is given to those results that involve the symmetry of graphs. As much as possible, the authors have tried to present results and proofs which are not often to be found in textbooks. Any student who has mastered 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

Preface	xi
Graphs and Groups: Preliminaries	1	(18)
Graphs and digraphs	1	(2)
Groups	3	(4)
Graphs and groups	7	(3)
Edge-automorphisms and line-graphs	10	(4)
A word on issues of computational complexity	14	(2)
Exercises	16	(1)
Notes and guide to references	17	(2)
Various Types of Graph Symmetry	19	(17)
Transitivity	19	(5)
Asymmetric graphs	24	(3)
Graph symmetries and the spectrum	27	(2)
Simple eigenvalues	29	(1)
Higher symmetry conditions	30	(3)
Exercises	33	(2)
Notes and guide to references	35	(1)
Cayley Graphs	36	(19)
Cayley colour graphs	36	(3)
Frucht's and Bouwer's Theorems	39	(3)
Cayley graphs and digraphs	42	(2)
Non-Cayley vertex-transitive graphs	44	(1)
Coset graphs and Sabidussi's Theorem	45	(2)
Hamiltonicity	47	(1)
Growth rates	48	(2)
Exercises	50	(2)
Notes and guide to references	52	(3)
Orbital Graphs and Strongly Regular Graphs	55	(11)
Definitions and basic properties	55	(4)
Rank 3 groups	59	(1)
Strongly regular graphs	60	(1)
The Integrality Condition	61	(2)
Moore Graphs	63	(1)
Exercises	64	(1)
Notes and guide to references	65	(1)
Graphical Regular Representations and Pseudosimilarity	66	(11)
Elementary results	66	(1)
Abelian groups	67	(1)
Pseudosimilarity	68	(1)
Some basic results	69	(2)
Several pairs pseudosimilar	71	(1)
Mutually pseudosimilar vertices	72	(1)
Exercises	73	(3)
Notes and guide to references	76	(1)
Products of Graphs	77	(11)
General products of graphs	78	(1)
Categorical product	79	(1)
Cartesian product	80	(3)
More products	83	(3)
Additional remarks	86	(1)
Exercises	86	(1)
Notes and guide to references	87	(1)
Special Classes of Vertex-Transitive Graphs and Digraphs	88	(14)
Generalised Petersen graphs	89	(4)
Kneser graphs and odd graphs	93	(1)
Metacirculant graphs	94	(2)
The quasi-Cayley graphs and digraphs	96	(3)
Exercises	99	(1)
Notes and guide to references	100	(2)
The Reconstruction Conjectures	102	(12)
Definitions	103	(2)
Some basic results	105	(5)
Maximal planar graphs	110	(1)
Exercises	111	(1)
Notes and guide to references	112	(2)
Reconstructing from Subdecks	114	(7)
The endvertex-deck	114	(2)
Reconstruction numbers	116	(1)
The characteristic polynomial deck	117	(2)
Exercises	119	(1)
Notes and guide to references	120	(1)
Counting Arguments in Vertex-Reconstruction	121	(8)
Kocay's Lemma	121	(2)
Counting spanning subgraphs	123	(3)
The characteristic and the chromatic polynomials	126	(1)
Exercises	127	(1)
Notes and guide to references	128	(1)
Counting Arguments in Edge-Reconstruction	129	(14)
Definitions and notation	129	(3)
Homomorphisms of structures	132	(3)
Lovasz' and Nash-Williams' Theorems	135	(3)
Extensions	138	(2)
Exercises	140	(1)
Notes and guide to references	141	(2)
Bibliography	143	(10)
List of Notation	153	(2)
Index of Terms and Definitions	155