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
$\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
    $\begingroup$ It seems this is known as the middle graph. $\endgroup$ – Juho Feb 21 '16 at 20:41

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.