On hamiltonian line-graphs
Gary Chartrand · Transactions of the American Mathematical Society · 1968
Introduction.The line-graph L(G) of a nonempty graph G is the graph whose point set can be put in one-to-one correspondence with the line set of G in such a way that two points of L(G) are adjacent if and only if the corresponding lines of G are adjacent.In this paper graphs whose line-graphs are eulerian or hamiltonian are investigated and characterizations of these graphs are given.Furthermore, necessary and sufficient conditions are presented for iterated line-graphs to be eulerian or hamiltonian.It is shown that for any connected graph G which is not a path, there exists an iterated line-graph of G which is hamiltonian.Some elementary results on line-graphs.In the course of the article, it will be necessary to refer to several basic facts concerning line-graphs.In this section these results are presented.All the proofs are straightforward and are therefore omitted.In addition a few definitions are given.If x is a Une of a graph G joining the points u and v, written x=uv, then we define the degree of x by deg zz+deg v-2.We note that if w ' the point of L(G) which corresponds to the line x, then the degree of w in L(G) equals the degree of x in G.A point or line is called odd or even depending on whether it has odd or even degree.If G is a connected graph having at least one line, then L(G) is also a connected graph.For the most part then, we restrict ourselves to connected graphs for otherwise each connected component can be treated individually.By L\G) we shall mean L(L(G)) and, in general, Ln(G)=L(Ln-\G)) for «^ 1, where L\G) and L°(G) stand for L(G) and G, respectively.Two classes of graphs which have easily determined line-graphs are the cycles and simple paths.In particular, the line-graph of a cycle is a cycle of the same length, and the line-graph of a simple path of length «, « ^ 1, is a simple path of length n -1.It therefore follows that if G is a path of length n, n J 1, then Ln(G) is the trivial path consisting of a single point while Lm(G) does not exist for m > n.It is not difficult to see that if G is a connected graph which is not a path, then Ln(G) exists for all positive integers «.Hence, if for some graph G, we wish to consider the infinite sequence {Ln(G)} of graphs, then G must not be a path.A bridge of a connected graph G is a line whose removal disconnects G, while a cutpoint of G is a point w of G such that the removal of w and all its incident lines