3.2. Line Graphs

The line graph  of a graph G is that graph whose vertices can be put in one-to-one correspondence with the edges of G in such a way that two vertices of  are adjacent iff the corresponding edges of G are adjacent.

In other words: A graph H is a line graph if there exists a graph G such that .

It is relatively easy to determine the number of vertices and the number of edges in the line graph  of a graph G in terms of easily computed quantities in G:

If given a graph  with degree sequence  and  is a graph of order  and size  then

How can we decide whether a given grap H is a line graph?

Several characterization of line graphs have been obtained, perhaps the best known of which is the „ forbidden subgraph" characterisat-ion due to Beineke (1968).

Theorem 3.5. A graph H is a line graph iff none of the next graphs is an induced subgraph of H.

A set X of edges in a graph is called a dominating set if every edge of G either belongs to X or is adjacent to an edge of X.