Graphs and Groups

==========================================================================

Chapter 7 Graphs and Groups

To aim to explore mathematical essence of graph theory further, the closed connection between graphs and groups will be discussed in this chapter. The reader who will read this chapter is supposed to familiarize himself with some basic concepts and methods of group theory.

As we have known from group theory that every finite set with an appropriate relation or operation there exists a group of permutations preserving the relation or operation. As a set with a given binary relation, of course, graph is no exception. We will see that every graph is associated with a group of permutations preserving adjacency on its vertex-set, called an automorphism group of the graph. On the other hand, we will also see, for every finite abstract group there exists a digraph, called Cayley graph, its color-preserving automorphism group, a subgroup of the automorphism group of the Cayley graph, is isomorphic to the group; there also exists an undirected graph, called Frucht graph, its automorphism group is isomorphic to the group, the latter answers a question proposed by K\"oning in 1936.

With the aid of the automorphism group, we will discuss an important class of graphs, vertex-transitive graphs, and investigate their structural properties. The Cayley graph, a vertex-transitive graph, can be constructed for a given finite group and a set of the group without the identity. The Frucht graph can be also constructed by making use of a Cayley digraph.

Graph theory has become an important analytical tool in group theory. In particular, in 1968, Higman and Sims discovered the well-known Higman-Sims group of order 44,352,000 by graph theoretical method. Since that time several other sporadic simple groups have been constructed as automorphism group of graphs. The interested reader is referred to a book by Biggs and White (1979). We will here introduce their applications in designs of interconnection networks.