4
$\begingroup$

Suppose we have a finite simple graph $G$. Call $\mathcal O$ the set of graphs without isolated vertices up to isomorphism whose line graph is isomorphic to $G$. Can $\mathcal O$ contain more than one element?

$\endgroup$
4
$\begingroup$

According to Wikipedia, "Hassler Whitney (1932) proved that with one exceptional case the structure of a connected graph G can be recovered completely from its line graph." The reference is given as Whitney, H. (1932), "Congruent graphs and the connectivity of graphs", American Journal of Mathematics 54 (1): 150–168, doi:10.2307/2371086, JSTOR 2371086.

There is also a reference to Harary, F. (1972), "8. Line Graphs", Graph Theory, Massachusetts: Addison-Wesley, pp. 71–83; it says, "Harary gives a simplified proof of this theorem by Jung."

Whitney's result is given as, "If the line graphs of two connected graphs are isomorphic, then the underlying graphs are isomorphic, except in the case of the triangle graph $K_3$ and the claw $K_{1,3}$, which have isomorphic line graphs but are not themselves isomorphic."

$\endgroup$
  • $\begingroup$ Excelent, thank you very much. this is exactly what I was looking for. $\endgroup$ – Jorge Fernández Hidalgo Jul 30 '14 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.