While reading the openbook "Algorithmic Graph Theory " I came by Definition 1.7 which is supposed to define what a line graph is , here is the definition:

Definition 1.7. Let $G=(V,E,h)$ be an unweighted multidigraph.The line graph of $G$ , denoted $\mathcal{L}(G)$, is the multidigraph whose vertices are the edges of $G$ and whose edges are $(e,e')$ where $h(e)=t(e')($for $ e, e' \in E)$.A similar definition holds if $G$ is undirected.

The above did not make any sense to me especially the whose vertices are edges of $G$

could anyone please clear up this definition?

  • $\begingroup$ As a start, to define $\mathcal L(G)$, the required datafor a graph must be specified. Among these is a set of vertices. We are allowed to take the set $E$ as this set. $\endgroup$ – Hagen von Eitzen Apr 3 '13 at 21:06
  • $\begingroup$ $h(e)$ is the start vertex of an edge, and $t(e)$ its target ? $\endgroup$ – Vincent Nivoliers Apr 3 '13 at 21:09
  • $\begingroup$ @HagenvonEitzen can a set of ordered pairs taken up as a set of vertices ? $\endgroup$ – metric-space Apr 3 '13 at 21:12
  • $\begingroup$ @VincentNivoliers $t(e)$ refers to the tail ,$h(e)$ refers to the head. $\endgroup$ – metric-space Apr 3 '13 at 21:13

To build a graph, you need two things. A set of vertices, and a set of edges. The vertices can be any set, and the edges are relations between these vertices, encoded by pairs of vertices. In your case, ordered pairs, since you are talking about directed graphs. To get back to your problem, we can illustrate the line graph as follows :

The vertices of your graph can be represented as cities, and the edges as roads. The graph is directed, which means the roads are only one way, and its a multigraph, which means that there can be several roads between the same cities. When you are at a given city, you can consider the different roads that are connected to your city, and move between cities using the roads.

Building the line graph corresponds now to consider that you no longer want to live in cities, but on roads. Now to go from one road to the other, you have to go through cities. One road is connected to an other if the second road starts from the city where the first road ends. Now you have a set of elements, the roads, and a set of connections between the roads. This is a graph, and it is the line graph.


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.