- W/Prof Cheryl Praeger
- A/Prof Michael Giudici

Feb 2008

Symmetric Graphs of Diameter Two

A graph consists of a set of objects, called vertices, together with a set of unordered pairs of distinct vertices, which are called edges. Two vertices which form an edge of the graph are said to be adjacent; an ordered pair of adjacent vertices is called an arc. An automorphism of a graph is a permutation of its vertex set that preserves the relation of adjacency and nonadjacency of vertices.

A graph is said to have diameter 2 if it is not a complete graph (i.e., not all pairs of vertices are adjacent), and if every pair of nonadjacent vertices are connected by a path of length 2. It is symmetric or arc-transitive if its group of automorphisms is transitive on the set of all arcs - that is, for any two distinct arcs (a,b) and (x,y), there is an automorphism g of the graph such that (a^g,b^g) = (x,y).

The purpose of this thesis is to examine the overall structure of symmetric graphs of diameter 2.

A graph is a model of an interconnection network, which is a system of nodes linked by communication channels. Examples of these are telecommunications and computer systems. In such a model, the parameters of the graph correspond to properties of the network, so that the problem of designing networks that possess features associated with efficient communication can be translated into the problem of constructing graphs with the corresponding properties.

Arc-transitive diameter 2 graphs are worthy of study for at least two reasons, namely: (1.) Their small diameter and symmetric structure make them desirable in network design, as described above; and (2.) They include some important and well-studied families of graphs, such as all symmetric strongly regular graphs (and in particular, the rank 3 graphs) and the Frobenius graphs.