Line Graph

• The line graph of a graph is the graph such that

• Line graphs for common families of graphs:

  • .
  • .
  • The only graphs where are the -regular graphs.
    • Proof: Let . We have
      Thus, there is an isomorphism between and pairs of edges in which are incident. A natural mapping is:
      Because it is an isomorphism, it is also invertible. This means each vertex is incident to only edges. Thus, the graph is regular.

• (Godsil 1.7.1) If is -regular, then is regular with degree .

  • Proof: Let be an edge in . Since it is -regular, it is incident to other edges from and respectively for a total of

• (Godsil e1.12) Any induced subgraph of a line graph is also a line graph.

• (Godsil 1.7.2) Krausz Characterization of Line Graphs A nonempty graph is a line graph if and only if its edge set can be partitioned into a set of cliques with the property that any vertex is in at most two cliques.

  • If is triangle-free, then all cliques are all maximal.

• (Godsil 1.7.3) Whitney’s Isomorphism Theorem Except for the pair , the following is true

  • Idea: There is a bijection between and the maximal cliques of .

• (Godsil 1.7.4) A graph is a line graph if and only if each induced subgraph of on at most six vertices is a line graph.

• (Godsil 1.7.5) If is a connected graph and is regular, then is regular or bipartite and semiregular.

  • Proof: If , and is -regular, then has edges incident to it. Adding itself to the degree counts, we get

    Consider arbitrary vertex . Let be the set of vertices of distance exactly from . We have that all of have the same degree. All of share the same degree, and so on. In general, we can partition the graph (by connectivity) into and .

    To show the theorem, consider two cases. If the degree of equals that of , then is regular by definition.

    This can only happen because of two adjacent vertices with the same degree (i.e., in an odd cycle). If the graph has no odd cycle, it is bipartite and by our characterization semiregular.

• (Godsil e1.21) If two trees have isomorphic line graphs then they are isomorphic.

  • Proof: Let be trees such that . Each vertex in bijectively maps to a maximum clique in . This bijectively maps to a maximum clique in preserving adjacencies within and between cliques. And, the maximum clique in bijectively maps to a vertex in . Thus, each vertex in can be made to bijectively map to and so

Links §

• Algebraic Graph Theory by Godsil and Royle

• Fundamental Constructs of Graph Theory

• Families of Graphs