Spectra of Group-Subgroup Pair Graphs

Graphs with large isoperimetric constants play an important role in cryptography because one can utilize such graphs to construct cryptographic hash functions. Ramanujan graphs are important optimal examples of such graphs, and known explicit construction of infinite families of Ramanujan graphs are given by Cayley graphs. A group–subgroup pair graph, which is a generalization of a Cayley graph, is defined for a given triplet consisting of finite group, its subgroup, and a suitable subset of the group. We study the spectra, that is the eigenvalues of the adjacency operators, of such graphs. In fact, we give an explicit formula of the eigenvalues of such graphs when the corresponding subgroups are abelian in terms of the characters of the subgroups as well as give a lower bound estimation for the second largest eigenvalues.