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

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


05C45 Eulerian and Hamiltonian graphs
05C99 Graph theory
Full Text: DOI Link


[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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.