Carregant...
Tipus de document
Treball de fi de grauData de publicació
Llicència de publicació
Si us plau utilitzeu sempre aquest identificador per citar o enllaçar aquest document: https://hdl.handle.net/2445/222195
On subgraphs of ninimal Cayley graphs
Títol de la revista
Autors
Director/Tutor
ISSN de la revista
Títol del volum
Recurs relacionat
Resum
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.
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.
Descripció
Treballs Finals de Grau de Matemàtiques, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2025, Director: Kolja Knauer
Matèries (anglès)
Citació
Col·leccions
Citació
SOTO GÓMEZ, Álvaro. On subgraphs of ninimal Cayley graphs. [consulta: 3 de gener de 2026]. [Disponible a: https://hdl.handle.net/2445/222195]