Publicado 28/08/2021
Palabras clave
- line graph,
- edge-complement graph,
- graph equation
Cómo citar
Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.
Resumen
A partir de un grafo $G$ se pueden construir grafos relacionados, como su grafo de líneas $L(G)$ y su grafo complemento de aristas $\overline{G}$. Después de mostrar cómo las propiedades de $G$ implican propiedades de $L(G)$, nos preguntamos cuán diferentes son los conceptos del grafo lineal $L(G)$ y el del grafo complemento de aristas $\overline{G}$, resolviendo la ecuación $L(G) \simeq \overline{G}$. Demostramos que la ecuación tiene solo dos soluciones. La prueba utiliza un argumento sobre el grado de los vértices de un grafo que permite reducir el número de posibles soluciones hasta poder comprobarlas algorítmicamente. Esto da una prueba alternativa a la de Aigner.