×

Topics in graph automorphisms and reconstruction. (English) Zbl 1038.05025

London Mathematical Society Student Texts 54. Cambridge: Cambridge University Press (ISBN 0-521-82151-7/hbk; 0-521-52903-4/pbk). xii, 159 p. (2003).
We have here a very suitable text for an undergraduate course in graph theory with emphasis on graph symmetry. It may therefore serve well as an accompaniment to a broader syllabus that includes some standard graph theory topics not covered here (e.g., connectivity and chromatic graph theory). Prerequisite is some background in basic combinatorics and elementary group theory and linear algebra. The style is eminently readable; many examples illustrate the concepts; each section is followed by relevant exercises. The distinctions between the vertex-group and the edge-group of a graph as well as between automorphism of abstract groups and automorphism of permutation groups is carefully maintained. The chapter headings are as follows: (1) Graphs and groups: preliminaries. (2) Various types of graph symmetry. (3) Cayley graphs. (4) Orbital graphs and strongly regular graphs. (5) Graphical regular representations and pseudosimilarity. (6) Products of graphs. (7) Special classes of vertex-transitive graphs and digraphs. (8) The reconstruction conjectures. (9) Reconstructing from subdecks. (10) Counting arguments in vertex-reconstruction. (11) Counting arguments in edge-reconstruction. Bibliography, List of notation, Index of terms and definitions.

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics

Software:

nauty; GRAPE
PDFBibTeX XMLCite