John claims that he and Gordon are confused by the various adjectives used by us graph symmetry people and how they relate to each other so I have decided to write some posts outlining the main ones and their importance. There is a nice diagram on wikipedia illustrating the relationship between the main ones and I will use that as the basis of my discussion.

Throughout I will use to denote a graph and to denote a group (unfortunately some authors use the reverse.) All graphs will be simple (that is, undirected, no multiple edges, and no loops) and finite. The full automorphism group of a graph, that is the group of all permutations of the set of vertices that take edges to edges, will be denoted by . I will use to denote the set of vertices, to denote the set of edges and to denote the set of arcs, that is the set of ordered pairs of adjacent vertices.

The first adjective is regular. A graph is called *regular* if each vertex has the same number of neighbours. This number is referred to as the *valency* of the graph.

A graph is called *vertex-transitive* if acts transitively on the set of vertices, that is, for all there exists an automorphism such that . Sometimes we wish to restrict our attention to a subgroup of and say that is -vertex-transitive if acts transitively on .

One consequence of a graph being vertex-transitive is that it is regular: if an automorphism maps to then it also maps the neighours of to the nieghbours of . However, not all regular graphs are vertex-transitive. In fact, it is even possible for a regular graph to have a trivial automorphism group, for example, the Frucht graph.

Continue reading “Graph symmetry”