On subgraphs of ninimal Cayley graphs

Abstract

In this paper, we aim to identify graphs that are not subgraphs of minimal Cayley graphs. Specifically, we will focus our study on cubic graphs. To this end, we first examine the fundamental properties of minimal Cayley graphs and establish two necessary conditions for a graph to be a subgraph of one. We then provide a proof of Spencer’s theorem. Later on, we analyze the subcase of the family of Generalized Petersen graphs by showing which of them are minimal Cayley graphs and demonstrating that, for certain parameters, generalized Petersen graphs are subgraphs of a minimal Cayley graph of the semidirect product of two cyclic groups. Finally, after covering the necessary theoretical groundwork, we will present and explain the algorithm developed for identifying prohibited graphs.

En aquest text, el nostre objectiu és identificar grafs que no són subgrafs de grafs de Cayley mínims. Concretament, centrarem el nostre estudi en els grafs cúbics. Per assolir aquest objectiu, primer examinarem les propietats fonamentals dels grafs de Cayley mínims i establirem dues condicions necessàries perquè un graf sigui un subgraf d’un d’aquests. A continuació, proporcionarem una demostració del teorema de Spencer. Posteriorment, analitzarem el subcàs de la família dels grafs generalitzats de Petersen, mostrant quins d’aquests són grafs de Cayley mínims i demostrant que, per a certs paràmetres, els grafs generalitzats de Petersen són subgrafs d’un graf de Cayley mínim del producte semidirecte de dos grups cíclics. Finalment, després de cobrir les bases teòriques necessàries, presentarem i explicarem l’algoritme desenvolupat per identificar grafs prohibits.