The Petersen Graph es un libro de matemáticas sobre el gráfico de Petersen y sus aplicaciones en la teoría de grafos . Fue escrito por Derek Holton y John Sheehan y publicado en 1993 por Cambridge University Press como volumen 7 de su serie de conferencias de la Sociedad Australiana de Matemáticas.
El gráfico de Petersen es un gráfico no dirigido con diez vértices y quince aristas, comúnmente dibujado como un pentagrama dentro de un pentágono , con los vértices correspondientes unidos entre sí. Tiene muchas propiedades matemáticas inusuales y con frecuencia se ha utilizado como contraejemplo de conjeturas en la teoría de grafos. [1] [2] El libro utiliza estas propiedades como excusa para cubrir varios temas avanzados en teoría de grafos donde este gráfico juega un papel importante. [1] [3] Está muy ilustrado e incluye tanto problemas abiertos sobre los temas que analiza como referencias detalladas a la literatura sobre estos problemas. [1] [4]
Después de un capítulo introductorio, los capítulos segundo y tercero se ocupan de la coloración de gráficos , la historia del teorema de los cuatro colores para los gráficos planos , su equivalencia con la coloración de 3 aristas de los gráficos cúbicos planos , los snarks (gráficos cúbicos que no tienen tales colores), y la conjetura de WT Tutte de que todo snark tiene el gráfico de Petersen como gráfico menor . Dos capítulos más tratan temas estrechamente relacionados, coincidencias perfectas (los conjuntos de aristas que pueden tener un solo color en una coloración de 3 aristas) y flujos en ninguna parte cero (el concepto dual de coloración de gráficos planos). El gráfico de Petersen aparece nuevamente en otra conjetura de Tutte, que cuando un gráfico sin puente no tiene el gráfico de Petersen como menor, debe tener un flujo 4 en ninguna parte cero. [3]
El capítulo seis del libro trata sobre jaulas , los gráficos regulares más pequeños sin ciclos más cortos que una longitud determinada. El gráfico de Petersen es un ejemplo: es el gráfico de 3 regulares más pequeño sin ciclos de longitud inferior a 5. El capítulo siete trata sobre los gráficos hipohamiltonianos , los gráficos que no tienen un ciclo hamiltoniano que pasa por todos los vértices pero que sí tienen ciclos por cada conjunto de todos los vértices menos uno; el gráfico de Petersen es el ejemplo más pequeño. El siguiente capítulo se refiere a las simetrías de las gráficas y a los tipos de gráficas definidas por sus simetrías, incluidas las gráficas transitivas de distancia y las gráficas fuertemente regulares (de las cuales la gráfica de Petersen es un ejemplo) [3] y las gráficas de Cayley (de las cuales es no). [1] El libro concluye con un capítulo final de temas diversos, demasiado pequeños para sus propios capítulos. [3]
El libro supone que sus lectores ya tienen cierta familiaridad con la teoría de grafos. [3] Puede utilizarse como obra de referencia para investigadores en esta área, [1] [2] o como base de un curso avanzado en teoría de grafos. [2] [3]
Aunque Carsten Thomassen describe el libro como "elegante", [4] y Robin Wilson evalúa su exposición como "en general buena", [2] el crítico Charles HC Little adopta el punto de vista opuesto, criticando su edición y parte de su notación matemática. , y con su incapacidad para discutir la red de combinaciones enteras de coincidencias perfectas, en las que el número de copias del gráfico de Petersen en los "ladrillos" de una determinada descomposición del gráfico juega un papel clave en el cálculo de la dimensión. [1] El crítico Ian Anderson señala la superficialidad de parte de su cobertura, pero concluye que el libro "logra dar una visión emocionante y entusiasta" de la teoría de grafos. [3]