Traversability in Line Graphs

In this chapter we look first at which line graphs are Eulerian and which graphs are the line graphs of Eulerian graphs, both of which have nice characterizations. We then turn to the subject of Hamiltonian graphs. It is not hard to show that the line graph of a Hamiltonian graph is Hamiltonian, but as one would expect, determining which line graphs are Hamiltonian is a difficult problem. The fourth section is devoted to aspects of an outstanding conjecture on this subject: if a line graph is 4-connected, then it is Hamiltonian. We then turn to iterated line graphs. After observing that unless a graph is a path, all of its iterations beyond some point are Hamiltonian, and the problem of determining when this first iteration occurs investigated in the last section.