Line Graphs and Beyond
International Conference on Applied Mathematics and Theoretical Computer Science
St. Xavier Catholic College of Engineering, Nagercoil, India
The line graph operation, in which the edges of one graph are taken as the vertices of a new graph, with adjacency preserved, is arguably the most interesting of graph transformations. In this survey, we will begin by looking at various characterizations of line graphs, focusing on results related to our set of nine forbidden subgraphs.
In contrast to many concepts in graph theory, the directed counterpart is quite different to the undirected concept, and we look at some of the differences between the two, including characterizations of line digraphs.
This will be followed by a discussion of some of the most important properties of line graphs, including planarity and Hamiltonicity.
Line graphs have been generalized in many interesting ways, and we conclude with some of our results on two of these: (a) the Krausz dimension, for which line graphs are those with value 1 or 2, and (b) super line graphs, in which the vertices correspond to sets with more than one edge.
Line graphs, super line graphs, line completion problem
Lowell Beineke (2013).
Line Graphs and Beyond. Presented at International Conference on Applied Mathematics and Theoretical Computer Science, St. Xavier Catholic College of Engineering, Nagercoil, India.