Eulerian subgraphs containing given vertices and hamiltonian line graphs (Q1377854): Difference between revisions

Let \(G\) be a graph and let \(D_1(G)\) be the set of vertices of degree 1 in \(G\). A graph is called an eulerian graph if it is connected and every vertex has even degree. An eulerian subgraph \(H\) of a graph \(G\) is called a dominating eulerian subgraph if \(G-V(H)\) is edgeless. The line graph of a graph \(G\), denoted by \(L(G)\), has \(E(G)\) as its vertex set, where two vertices in \(L(G)\) are adjacent if and only if the corresponding edges in \(G\) are adjacent. It is known [\textit{F. Harary} and \textit{C. St. J. A. Nash-Williams}, Can. Math. Bull. 8, 701-709 (1965; Zbl 0136.44704)] that the line graph \(L(G)\) of a graph \(G\) with \(| E(G) |\geq 3\) is hamiltonian if and only if \(G\) has a dominating eulerian subgraph. \textit{H. J. Veldman} [Discrete Math. 124, No. 1-3, 229-239 (1994; Zbl 0789.05061)] proved that if \(G-D_1(G)\) is a 2-edge-connected simple graph with \(n\) vertices and if for every edge \(xy\in E(G) \), \(d(x)+ d(y)> (2n)/5-2\), then for \(n\) large, \(L(G)\) is hamiltonian. In this paper, using Catlin's reduction method and a similar idea of Veldman, the author shows that if \(G-D_1(G)\) is a 2-edge-connected simple graph with \(n\) vertices and if for every edge \(xy\in E(G)\), \(\max \{d(x), d(y)\}\geq n/5-1\), then for \(n\) large, \(L(G)\) is hamiltonian with the exception of a class of well-characterized graphs. This result implies Veldman's theorem.