ABSTRACT

Mark E. Watkins, Syracuse University

6.1.1 The Automorphism Group of a Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 590 6.1.2 Graphs with Given Group . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592 6.1.3 Groups of Graph Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594 6.1.4 Transitivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 596 6.1.5 s-Regularity and s-Transitivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599 6.1.6 Graphical Regular Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 600 6.1.7 Primitivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 602 6.1.8 More Automorphisms of Infinite Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 603 6.1.9 Distinguishability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 608 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611

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 are locally finite, i.e., all valences will be presumed to be finite, although they may be arbitrarily large.