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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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$.

Improve this answer
$\endgroup$
2
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .