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.

  • $\begingroup$ 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$. $\endgroup$ – Morgan Rodgers Oct 6 '18 at 16:03
  • $\begingroup$ 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? $\endgroup$ – Lucas Oct 6 '18 at 16:12
  • $\begingroup$ I did not know whether you were allowing loops. In that case replace two regular with "every vertex has exactly two neighbors". $\endgroup$ – 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$.

  • $\begingroup$ 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 $\endgroup$ – Lucas Oct 6 '18 at 16:18
  • $\begingroup$ @Lucas You showed yourself that it doesn't work on $P_2$. An edge can't dangle! $\endgroup$ – Parcly Taxel Oct 6 '18 at 16:19
  • $\begingroup$ @Lucas The "proof" is that an edge by definition is adjacent to exactly two vertices. You turn a vertex into an edge with exactly the same adjacencies, there is of course a problem if there are more than two vertices in the new graph adjacent to this edge. $\endgroup$ – Morgan Rodgers Oct 6 '18 at 16:20
  • $\begingroup$ 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? $\endgroup$ – Lucas Oct 6 '18 at 16:23
  • $\begingroup$ @Lucas At a degree-4 vertex in $G$, connecting the four edges that lead into it in $H$ would be ambiguous. $\endgroup$ – Parcly Taxel Oct 6 '18 at 16:25

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.