A study of the Structural Properties of finite $G$-graphs and their Characterisation

Abstract

The $G$-graph $\Gamma (G,S)$ is a graph from the group $G$ generated by $S\subseteq G$, where the vertices are the right cosets of the cyclic subgroups $⟨s⟩,s\in 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 finite $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 configurations. 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 finite $G$-graphs. As an application, we compute the energy of these graphs. We also present some preliminary results on infinite $G$-graphs where we consider the $G$-graphs of the infinite group $S{L}_2(\mathbb{Z})$ and an infinite non-Abelian matrix group.

This is an MPhil thesis presented to the University of Ghana