I was wondering if there is a name for this construction: Take a graph $G$ and construct a new graph $G'$ in which the edges of $G$ now become vertices, and "vertices become edges" in the sense that vertices are joined by edge in $G'$ if they as edges in $G$ shared a common vertex.

More precisely: Given a graph $G=(V=\{v_1,v_2,\dots,v_n\},E=\{e_1,e_2,\dots,e_k\})$ where each $e_i=\{u,v\}\subset V$ we define the graph $G'=(V'=\{e_1,e_2,\dots,e_k\},E')$ so that $\{e_i,e_j\}\in E' \iff e_i\cap e_j\neq\emptyset$.

I don't know if this can be used for anything (my guess would be it can't) it just came to my mind and thought that perhaps this has a name.


This is called the line graph of $G$. It actually has a wide variety of uses, as seen on that Wikipedia page, and the terminology is sufficiently standard that you should be able to mention it in a paper without defining it.

| cite | improve this answer | |

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.