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.