A Study of the Structural Properties of Finite G-Graphs and their Characterisation.

Abstract

The G-graph 􀀀(G; S) is a graph from the group G generated by S _ G, where the vertices are the right cosets of the cyclic subgroups hsi; s 2 S with k-edges between two distinct cosets if there is an intersection of k elements. In this thesis, after presenting some important properties of G-graphs, we show how the G-graph depends on the generating set of the group. We give the G-graphs of the symmetric group, alternating group and the semi-dihedral group with respect to various generating sets. We give a characterisation of _nite G-graphs; in the general case and a bipartite case. Using these characterisations, we give several classes of graphs that are G-graphs. For instance, we consider the Turán graphs, the platonic graphs and biregular graphs such as the Levi graphs of geometric con_gurations. We emphasis the structural properties of G-graphs and their relations to the group G and the generating set S. As preliminary results for further studies, we give the adjacency matrix and spectrum of various _nite G-graphs. As an application, we compute the energy of these graphs. We also present some preliminary results on in_nite G-graphs where we consider the G-graphs of the in_nite group SL2(Z) and an in_nite non-Abelian matrix group.