On the ubiquity of the Petersen Graph : a journey through History, properties, and applications

Abstract

Esta tesis se centra en la factorización de grafos cúbicos, con especial énfasis en el grafo de Petersen y en familias relacionadas, como los snarks, los grafos generalizados de Petersen (𝐺𝑃) y los nanotubos de carbono (𝑁𝑛). Se exploran conceptos y propiedades vinculadas al coloreo de grafos —particularmente el coloreo de aristas—, al conteo de ciclos —con atención al girth, la hamiltonianidad y la hipohamiltonianidad—, así como a la conectividad —𝑘-arista-conectividad y 𝑘-arista-conectividad cíclica. Junto con la exposición teórica, se incluye un análisis histórico que sitúa estas propiedades en su contexto original, con el fin de comprender mejor su desarrollo.

Asimismo, se presentan implementaciones interactivas que permiten manipular parámetros de los grafos 𝐺𝑃, visualizar factorizaciones y realizar conteo de ciclos. Dichas implementaciones fueron desarrolladas desde cero, sin el uso de librerías de teoría de grafos (excepto aquellas para visualización), con el propósito de profundizar en las propiedades hasta el punto de poder codificarlas directamente.

Finalmente, se estudia la representación, dentro de la teoría de grafos, de ciertas estructuras químicas de gran interés: los fullerenos, en particular los nanotubos de carbono. El objetivo principal es el conteo de emparejamientos perfectos en estas estructuras. Para ello, se emplean autómatas y el método de Schützenberger en el conteo de ciclos hamiltonianos, lo que permite obtener una cota inferior del número de emparejamientos perfectos en los 𝑁𝑛, mostrando que los mostrando que los nanotubos de carbono son estables y poseen más ciclos hamiltonianos que los grafos GP(2m,2) (Texto tomado de la fuente).

This thesis investigates the factorization of cubic graphs, with particular emphasis on the Petersen graph, as well as on families of graphs closely related to it, such as snarks, generalized Petersen graphs (𝐺𝑃), and carbon nanotubes (𝑁𝑛). The study focuses on several key aspects of graph theory, including graph coloring—with special attention to edge coloring—, cycle enumeration—emphasizing girth, Hamiltonicity, and hypohamiltonicity—, and connectivity, in particular 𝑘-edge-connectivity and cyclic 𝑘-edge-connectivity. Alongside the formal discussion of these properties, their historical development is also examined in order to provide a deeper contextual understanding.

The document further includes interactive code implementations that allow one to manipulate the parameters of 𝐺𝑃 graphs, visualize their factorizations, and analyze cycle counts. These codes were developed entirely from scratch, without the aid of graph theory libraries (except for visualization purposes), with the aim of achieving a thorough understanding of these properties, making their implementation possible without external tools.

All these considerations serve to study the representation, within graph theory, of fascinating chemical structures: fullerenes, and in particular carbon nanotubes. The main goal is to count the number of perfect matchings in these structures. To accomplish this, automata and the Schützenberger method are employed to enumerate Hamiltonian cycles, thereby providing a lower bound for the number of perfect matchings in 𝑁𝑛. This analysis demonstrates that carbon nanotubes are stable and contain more Hamiltonian cycles than the graphs GP(2m,2).