Handbook of Graph Theory, 2nd Edition

Chapter 6

Algebraic Graph Theory

Section 6.1 Automorphisms

Mark E. Watkins

Syracuse University

Introduction

An automorphism of a graph is a permutation of its vertex set that preserves incidence of vertices and edges. Under composition, the set of automorphisms of a graph forms a group that gives much information about both the local and the global structure of the graph. It may determine the graph's connectivity structure (Section 4.2) and the kinds of surfaces in which it may be embedded (Sections 7.1, 7.5). It is indispensable for counting the number of essentially “distinct” graphs with a variety of different properties (Section 6.3). In this section one will also encounter infinite graphs. It will usually be assumed that the infinite graphs ...