2 - Forbidden subgraphs

Summary

In this chapter we extend some structural characterizations of line graphs to generalized line graphs, with an emphasis on the technique of forbidden subgraphs. We describe a collection of minimal forbidden subgraphs for graphs whose smallest eigenvalue is at least —2, and we note some implications concerning the characterization of certain graphs by their spectra.

Line graphs

In this section we discuss characterizations of line graphs and the extent to which a root graph is determined by its line graph. We give three characterizations of line graphs, two of which will be extended to generalized line graphs in Section 2.3. The first, due to J. Krausz, is in terms of an edge-covering by cliques (complete subgraphs).

Theorem 2.1.1 [Kra]. A graph is a line graph if and only if its edge set can be partitioned into non-trivial cliques such that:

(i) two cliques have at most one vertex in common;

(ii) each vertex is in at most two cliques.

The proof of Krausz's theorem is not difficult (see, for example, [Har]): in a line graph L(G), a non-trivial clique K(v) arises from each vertex v of degree at least 2 in G, and the collection of all such cliques satisfies (i) and (ii). For the converse, given a collection C of non-trivial cliques satisfying (i) and (ii), we add to C a trivial clique for every vertex in just one clique of C, and construct a root graph as the intersection graph on the enlarged collection of cliques. In this way we establish a one-to-one correspondence between root graphs and systems of cliques satisfying conditions (i) and (ii). Such systems are said to be complete.