A graph equation between the line graph and the edge-complement graph
Senja Barthel, Fabio Buccoliero · VU Research Portal · 2021
From a graph G related graphs can be constructed, such as its line graph L(G) and its edge-complement graph \\bar{G}. After showing how properties of G imply properties of L(G), we ask how different the concepts of the line graph and that of the edge-complement graph are, by solving the equation L(G)≃\\bar{G}. We show that the equation has only two solutions. The proof uses an argument on the degree of the vertices of a graph that allows to reduce the number of possible solutions until they can be checked algorithmically. This gives an alternative proof to the one by Aigner.