Grafos de aristas

Abstract

El objetivo de este Trabajo Fin de Grado es el estudio de los grafos de aristas (line graphs en inglés, aunque también se pueden denominar con otros términos como derived graphs o interchange graph), obtenidos a partir de un grafo dado mediante una sencilla transformación: cambiando sus aristas por vértices, y haciendo que dos vértices estén unidos por una arista si las aristas correspondientes del grafo original correspondientes a dichos vértices tienen un vértice en común. Se demostrarán los Teoremas de Beineke y Whitney sobre caracterización e isomorfismos, y se abordarán distintos problemas de la Teoría de Grafos aplicados al caso particular de los grafos de aristas, como la descripción de los grafos de aristas de algunas familias concretas, el comportamiento de estos grafos al iterar, el rango de los autovalores de dichos grafos, la relación entre grafos eulerianos y hamiltonianos con los grafos de aristas, y los cálculos del número, índice y polinomio cromático para este conjunto de grafos.