Rose M. Blanding
Advisor: Dr. Patti Frazer Lock
SLU Festival of Science 2001 Oral Presentation
Properties of Line Graphs
My independent study concentrates on a field of
graph theory called line graphs. In graph theory, a graph consists
of a set of vertices and edges. The line graph is a manipulation
of these vertices and edges to create a new graph. The method for
drawing out the line graph L(G) of a graph G is shown below.
The line graph L(G) of a graph G is defined as:
1. The vertices of L(G) correspond to the
edges of G.
2. Two vertices in L(G) are adjacent iff
the corresponding edges in G are adjacent.
The number of edges in a graph G is equal to the
number of vertices in its line graph L(G). The number of edges in
a line graph is equal to [(the sum of the degrees for each edge uv)-2].
I have investigated line graphs of special classes
of graphs, such as cycle graphs, path graphs, and star graphs.
For cycle graphs: when G = Cn, L(G) = Cn
For path graphs: when G = Pn, L(G) = Pn-1
For star graphs: when G = Kn,1, L(G) = Kn
There is also a method for drawing a graph from
it’s line graph. This method is known as a Krausz decomposition.
Theorem: A nonempty graph H is a line
graph iff E(H) can be partitioned into subsets such that:
a) the subgraph induced by each member of
the partition is complete and
b)
no vertex of H lies in more than two of these induced subgraphs
Bipartite Graphs: I will discuss the
connection between line graphs of bipartite graphs and a class of graphs
known as ‘board graphs’.