Line graph
De Wikipedia, l'encyclopédie encyclopedia
En théorie des graphes, le line graph L(G) d'un graphe non orienté G, est un graphe qui représente la relation d'adjacence entre les arêtes de G. Le nom line graph vient d'un article de Harary et Norman publié en 1960[1]. La même construction avait cependant déjà été utilisée par Whitney en 1932 et Krausz en 1943[2],[3]. Il est également appelé graphe adjoint[4].
Un des premiers et des plus importants théorèmes sur les line graphs est énoncé par Hassler Whitney en 1932, qui prouve qu'en dehors d'un unique cas exceptionnel, la structure de G peut être entièrement retrouvée à partir de L(G) dans le cas des graphes connexes[2].