1
$\begingroup$

Let $G=(V,E)$ be an undirected graph. We form a graph $H=(V',E')$ from $G$ such that

  • $V' = V \cup \{ w_e \mid e \in E \}$, and
  • $E' = \{ aw_e, bw_e \mid ab = e \in E \} \cup \{ w_e w_f \mid e,f \text{ are adjacent edges in }G \}$.

Informally, $H$ is built from $G$ by subdividing each edge, and by putting an edge between two newly created vertices iff the corresponding edges are adjacent in $G$.

The above construction feels quite natural. Does it have a name? It seems like some kind of a variation of the line graph.

$\endgroup$

2 Answers 2

2
$\begingroup$

Your graph is a subgraph of the total graph of $G$. Both graphs have the same vertex set, and each edge in your graph is an edge in the total graph, but yours is missing edges for all the vertex-vertex adjacencies in $G$.

$\endgroup$
2
$\begingroup$

The graph $H$ is isomorphic to the intersection graph of $V\cup E$.

$\endgroup$
1
  • 1
    $\begingroup$ It seems this is known as the middle graph. $\endgroup$
    – Juho
    Feb 21, 2016 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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