Vol. 2 (2021): Proceedings of the 3rd BYMAT Conference
Artículos

A graph equation between the line graph and the edge-complement graph

Senja Barthel
Vrije Universiteit Amsterdam
Fabio Buccoliero
Vrije Universiteit Amsterdam
Cover for TEMat monográficos, 2 (2021): Proceedings of the 3rd BYMat Conference

Publicado 28/08/2021

Palabras clave

  • line graph,
  • edge-complement graph,
  • graph equation

Cómo citar

Barthel, Senja, y Buccoliero, Fabio. «A graph equation between the line graph and the edge-complement graph». En: TEMat monográficos, 2 (2021): Proceedings of the 3rd BYMAT Conference, págs. 231-234. ISSN: 2660-6003.URL: https://temat.es/monograficos/article/view/vol2-p231.

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.