# Is there a name for this graph?

Say we have a graph $$G=(V(G),E(G))$$, where $$V(G)$$ is the vertex set of $$G$$ and $$E(G)$$ is the edge set of $$G$$. Define a graph $$H$$ which preserves all adjacency relations, $$V(G)=E(H)$$ and $$V(H)=E(G)$$. Is there a name for $$H$$?

I should mention that I am not entirely sure that the previous definition is correct, so here's an intuitive explanation on what I'm thinking of. For example, say we have $$G=C_k$$ (the cycle of order $$k$$), so that $$V(G)=\{v_1,v_2,\ldots,v_k\}$$ and $$E$$ consists of $$v_iv_{i+1}$$ (with indices taken modulo $$k$$). Then the graph $$H$$ in this case would be again just $$C_k$$ with different vertex/edge labellings.

As another example, the path of order two $$G=P_2$$ would have a corresponding graph $$H$$ which has one vertex (since $$G$$ has one edge) and two edges (since $$G$$ has two vertices). In this case, however, I'm not sure that $$H$$ is well defined since it's not clear what two vertices these two edges are incident with.

So, is this a well-established concept for most graphs? When is it not well defined? Is there a name for this graph $$H$$ corresponding to $$G$$? Thanks in advance.

• You won't get a graph by doing this, unless $G$ is a 2-regular. (in which case this is the line graph). You could work around vertices of degree one by turning them into edges which are loops, but you will still have problems with vertices of degree $>2$. – Morgan Rodgers Oct 6 '18 at 16:03
• What about the graph with one vertex and two loops? This graph is $4$-regular, but doesn't the graph with two vertices and one edge incident with both vertices fit the definition? – Lucas Oct 6 '18 at 16:12
• I did not know whether you were allowing loops. In that case replace two regular with "every vertex has exactly two neighbors". – Morgan Rodgers Oct 6 '18 at 16:22

Your definition of $$E(H)$$ runs into problems with non-degree-2 vertices in $$G$$, as mentioned in comments. But if this change is made to the definition of $$E(H)$$:
two vertices of $$H$$ have an edge between iff the corresponding edges in $$G$$ share a vertex
then $$H$$ is the line graph of $$G$$.
• Is there a proof that the definition I gave doesn't work if $G$ isn't $2$-regular? Also, why does the graph I provided in the comments previously not work? Many thanks in advance – Lucas Oct 6 '18 at 16:18
• @Lucas You showed yourself that it doesn't work on $P_2$. An edge can't dangle! – Parcly Taxel Oct 6 '18 at 16:19
• I don't see how the "dangling edge" issue generalises though. I can tell why there are issues if for some $v\in V(G)$, $d(v)=1$, but why can't it work for $d(v)=4$ for the graph I gave? Could you explain why it doesn't fit the requirements? – Lucas Oct 6 '18 at 16:23
• @Lucas At a degree-4 vertex in $G$, connecting the four edges that lead into it in $H$ would be ambiguous. – Parcly Taxel Oct 6 '18 at 16:25