A result on Hamiltonian line graphs involving restrictions on induced subgraphs. (English) Zbl 0651.05049

Veldman, H. J.

J. Graph Theory 12, No. 3, 413-420 (1988).

Author’s abstract: “It is shown that the existence of a Hamilton cycle in the line graph of a graph G can be ensured by imposing certain restrictions on certain induced subgraphs of G. Thereby a number of known results on Hamiltonian line graphs are improved, including the earliest results in terms of vertex degrees. One particular consequence is that every graph of diameter 2 and order at least 4 has a Hamiltonian line graph.”
As a consequence of the main result in this paper it is deduced that L(G) is Hamiltonian for every graph G of order \(n\geq 4\) such that \(d(u)+d(v)\geq n-1\) holds either for every pair u, v of nonadjacent vertices, either for every edge uv\(\in E(G)\neq \emptyset\) whenever \(G\not\cong P_ 4\).

Reviewer: I.Tomescu

MSC:

05C45	Eulerian and Hamiltonian graphs
05C99	Graph theory

Keywords:

induced subgraphs; Hamiltonian line graphs

References:

[1]	Benhocine, J. Graph Theory 10 pp 411– (1986)
[2]	and , Graph Theory with Applications. Macmillan, London and Elsevier, New York (1976). · Zbl 1226.05083
[3]	Broersma, Ars Combinat. 23 pp 5– (1987)
[4]	Brualdi, J. Graph Theory 5 pp 307– (1981)
[5]	Contractions of graphs with no spanning eulerian subgraphs. Preprint (1986).
[6]	Catlin, J. Graph Theory 12 pp 29– (1988)
[7]	Spanning eulerian subgraphs and matchings. Preprint (1986).
[8]	Clark, J. Graph Theory 8 pp 303– (1984)
[9]	Harary, Can. Math. Bull. 8 pp 701– (1965) · Zbl 0136.44704
[10]	Lesniak-Foster, Can. Math. Bull. 20 pp 215– (1977) · Zbl 0357.05060
[11]	Oberly, J. Graph Theory 3 pp 351– (1979)
[12]	Veldman, J. Graph Theory 10 pp 23– (1986)