%\documentstyle[11pt]{article} \documentclass[12pt]{article} \usepackage{e-jc} \usepackage{amsmath,amsthm} %\renewcommand{\baselinestretch}{1.25} %\setlength{\textwidth}{6in} %\setlength{\textheight}{8.7in} %\setlength{\topmargin}{-0.5in} %\oddsidemargin=0.30 in %0.28 %\pagestyle{myheadings} %\markright{Spanning and dominating closed trails} \newcommand{\F}{\mbox{$\cal F$}} \newcommand{\B}{\mbox{$\cal B$}} \newcommand{\G}{\mbox{$G/\pi$}} \newcommand{\K}{\mbox{$\kappa'(G)$}} \newcommand{\SL}{\mbox{$\cal S\!L$}} \newcommand{\C}{\mbox{$\cal C\!L$}} \newcommand{\D}{\mbox{$D_{2}(G)$}} \newcommand{\DD}{\mbox{$|D_{2}(G)|$}} \newcommand{\f}{\mbox{$\cal F$}} \newcommand{\A}{\mbox{$\alpha$}} \newcommand{\ST}{\mbox{$\cal S\!T$}} \begin{document} \title{Lai's conditions for spanning and dominating closed trails} \author{Wei-Guo Chen\\ \small Guangdong Economic Information Center\\[-0.8ex] \small Guangzhou, P. R. China\\ \small\tt chen.0815@139.com\\ \and Zhi-Hong Chen\thanks{Research is supported by Butler University Academic Grant (2014)}\\ \small Department of Computer Science\\[-0.8ex] \small Butler University\\[-0.8ex] \small Indianapolis, IN 46208, U.S.A. \\ \small\tt chen@butler.edu\\ \and Mei Lu\\ \small Department of Mathematics\\[-0.8ex] \small Tsinghua University\\[-0.8ex] \small Beijing, P. R. China\\ \small \tt mlu@math.tsinghua.edu.cn } \date{} \maketitle \begin{abstract} A graph is supereulerian if it has a spanning closed trail. For an integer $r$, let ${\cal Q}_0(r)$ be the family of 3-edge-connected nonsupereulerian graphs of order at most $r$. For a graph $G$, define $\delta_L(G)=\min\{\max\{d(u), d(v) \}| \ \mbox{ for any $uv\in E(G)$} \}$. For a given integer $p\ge 2$ and a given real number $\epsilon$, a graph $G$ of order $n$ is said to satisfy a Lai's condition if $\delta_L(G)\ge \frac{n}{p}-\epsilon$. In this paper, we show that if $G$ is a 3-edge-connected graph of order $n$ with $\delta_L(G)\ge \frac{n}{p}-\epsilon$, then there is an integer $N(p, \epsilon)$ such that when $n> N(p,\epsilon)$, $G$ is supereulerian if and only if $G$ is not a graph obtained from a graph $G_p$ in the finite family ${\cal Q}_0(3p-5)$ by replacing some vertices in $G_p$ with nontrivial graphs. Results on the best possible Lai's conditions for Hamiltonian line graphs of 3-edge-connected graphs or 3-edge-connected supereulerian graphs are given, which are improvements of the results in [J. Graph Theorey 42(2003) 308-319] and in [Discrete Mathematics, 310(2010) 2455-2459]. \vskip 0.1 in \bigskip\noindent \textbf{Keywords:} Degree conditions, Spanning and dominating closed trails, Hamiltonian line graphs, Collapsible graphs %\vskip 0.1 in %%\noindent {\small \bf AMS Subject Classifications}. 05C45, 05C38, 05C35 \end{abstract} \section{Introduction} We follow Bondy and Murty \cite{BoMu76} for terms and notations, unless otherwise stated. Graphs considered in this paper are finite and loopless, but multiple edges are allowed. As in \cite{BoMu76}, $\kappa'(G)$ and $d_G(v)$ (or $d(v)$) denote the edge-connectivity of $G$ and the degree of a vertex $v$ in $G$, respectively. The maximum size of a matching in $G$ is denoted by $\alpha'(G)$. Let $O(G)$ be the set of vertices of odd degree in $G$. A connected graph $G$ is {\it Eulerian} if $O(G)=\emptyset$. An Eulerian subgraph $H$ in a graph $G$ is called a {\bf closed trail}; and is called a {\bf spanning closed trail} of $G$ if $V(H)=V(G)$; and is called a {\bf dominating closed trail} of $G$ if $G - V(H)$ is edgeless. A graph is {\it supereulerian} if it has a spanning closed trail. We use $\SL$ denote the family of supereulerian graphs. A graph $G$ is {\it collapsible} if for any even subset $R\subseteq V(G)$ or $R=\emptyset$, $G$ has a spanning connected subgraph $H_R$ with $O(H_R)=R$. We use $\C$ denote the family of collapsible graphs. Thus, $\C\subset \SL$. \vskip 0.1 in \subsection*{Catlin's reduction method} Let $G$ be a graph and let $X \subseteq E(G)$. The {\bf contraction} $G/X$ is the graph obtained from $G$ by identifying the two ends of each edge in $X$ and then deleting the resulting loops. A graph is {\bf trivial} if it is edgeless. If $H$ is a subgraph of $G$, then we write $G/H$ for $G/E(H)$. If $H$ is a connected subgraph of $G$, and if $v_H$ denotes the vertex in $G/H$ to which $H$ is contracted, then $H$ is called the {\bf preimage} of $v_H$. A vertex $v$ in a contraction of $G$ is {\bf nontrivial} if $v$ has a nontrivial preimage. If $G_0 = G/X$ and if every vertex of $G_0$ is a nontrivial vertex, then $G_0$ is a {\bf nontrivial contraction} of $G$. In \cite{Catl88}, Catlin showed that every graph $G$ has a unique collection of pairwise disjoint maximal collapsible subgraphs $H_1, H_2, \cdots, H_c$ such that $V(G)=\bigcup_{i=1}^cV(H_i)$. The {\bf reduction} of $G$ is $G' = G/(\cup_{i=1}^c H_i)$, the graph obtained from $G$ by contracting all nontrivial maximal collapsible subgraphs of $G$. A graph $G$ is {\bf reduced} if $G'=G$. \vskip 0.1 in For an integer $r$, let ${\cal Q}_0(r)$ be the set of 3-edge-connected reduced nonsupereulerian graphs of order at most $r$. In this paper, we use $P$ for the Petersen graph and use $P_{14}$ for the graph in Figure 1.1. It is known that $Q_0(13)=\{P\}$ and $Q_0(14)=\{P, P_{14}\}$ \cite{C1}. $$ \setlength{\unitlength}{.7pt} \begin{picture}(160,80)(-10,0) \put(-50,50){$P_{14}$} \multiput(0,50)(14,0){2}{\circle*{3}} \put(66,50){\circle*{3}} \put(81,50){\circle*{3}} \multiput(0,50)(14,0){2}{\line(1,0){20}} \put(40,80){\circle*{3}} \put(14,15){\circle*{3}} \multiput(26,30)(28,0){2}{\circle*{3}} \put(81,30){\circle*{3}} \put(81,70){\circle*3} \put(101,40){\circle*3} \put(101,60){\circle*3} \put(101,40){\line(-2,-1){20}} \put(101,40){\line(-2,1){20}} \put(101,40){\line(-2,3){20}} \put(101,60){\line(-2,-1){20}} \put(101,60){\line(-2,1){20}} \put(101,60){\line(-2,-3){20}} \put(66,15){\line(1,1){15}} \put(66,50){\line(1,0){15}} \put(0,50){\line(2,-5){14}} \put(0,50){\line(4,3){40}} \put(40,65){\circle*{3}} \put(40,65){\line(0,1){15}} \put(26,30){\line(2,5){14}} \put(40,65){\line(2,-5){14}} \put(26,30){\line(2,1){40}} \put(14,50){\line(2,-1){40}} \put(14,50){\line(1,0){52}} \put(66,15){\circle*{3}} \put(54,30){\line(4,-5){12}} \put(14,15){\line(3,4){11}} \put(14,15){\line(1,0){52}} \put(40,80){\line(4,-1){40}} \put(20, -10){Figure 1.1} \end{picture} $$ \vskip 0.1 in For a graph $G$, the line graph $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. The following theorem relates dominating closed trails and Hamiltonian line graphs. \vskip 0.1 in \noindent {\bf Theorem A} (Harary and Nash-Williams \cite{HaNa65}). Let $G$ be a graph with at least three edges. Then $L(G)$ is Hamiltonian if and only if $G$ has a dominating closed trail. \vskip 0.1 in Graphs with spanning or dominating closed trails have been studied by many authors. The subject is closely related to the study on Hamiltonian graphs \cite{Ry}, Chinese Postman problem \cite{BoST77} and Traveling Salesman problem \cite{TSP}. Pulleyblank \cite{Pull79} showed that the problem of determining if a graph $G$ is supereulerian is NP-complete. Like the studies on many NP-complete problems in graph theory, various degree conditions have been studied for problems related to supereulerian graphs. For a graph $G$, we define\\ \indent $\delta(G)=\min\{d(v)\ |\mbox{ for any }\ v\in V(G)\}$;\\ \indent $\sigma_2(G)=\min\{d(u)+d(v)\ | \mbox{ for any}\ uv\not \in E(G)\}$; \\ \indent $\sigma_{t}(G)=\min\{ \Sigma_{i=1}^{t} d(v_i)\ | \ \{ v_1, v_2, \cdots, v_t\}\ \mbox{is independent in $G$}\ (t\ge 2) \ \}$;\\ \indent $\delta_F(G)=\min\{ \max\{ d(u),\ d(v) \}\ |\ \mbox{ for any $u, v \in V(G)$ with $dist(u, v)=2$}\}$;\\ \indent $\overline{\sigma}_2(G)=\min\{ d(u)+d(v) \ | \ \mbox{for every edge $uv\in E(G)$} \}$;\\ \indent $\delta_L(G)=\min\{ \max \{d(u), d(v)\} | \ \mbox{ for every edge } uv \in E(G)\}$. \vskip 0.1 in These are all the degree parameters that have been studied for graphs with spanning or dominating closed trails (see \cite{Brualdi,Catl88, Cat2, Chen2, CL2, LaiH98, Lesniak, Veld94}). Let \\ \centerline{$\Omega(G)=\{\delta(G), \sigma_2(G), \sigma_{t}(G), \delta_F(G), \overline{\sigma}_2(G), \delta_L(G)\}.$ } \vskip 0.1 in For a given integer $p$ and a given real number $\epsilon$, a graph $G$ of order $n$ is said to satisfy a {\bf Lai's degree condition} or {\bf Lai's condition} if \begin{equation} \delta_L(G) \ge \frac{n}{p}-\epsilon. \end{equation} Such degree condition was first considered by Lai \cite{LaiH98} in the study of Hamiltonian line graphs. Obviously, if $\overline{\sigma}_2(G)\ge 2(\frac{n}{p}-\epsilon)$, then $\delta_L(G)\ge \frac{n}{p}-\epsilon$. \vskip 0.1in Here are some prior results related to Lai's conditions. Settling a conjecture posted in \cite{BCKV86}, Veldman \cite{Veld94} proved the following. \\ \noindent {\bf Theorem B} (Veldman \cite{Veld94}). Let $G$ be a 2-edge-connected simple graph on $n$ vertices. If \begin{equation} \overline{\sigma}_2(G) > \frac{2n}{5} - 2, \end{equation} then, for $n$ sufficiently large, $L(G)$ is Hamiltonian. \vskip 0.1 in Condition (1) with $p=5$ and $\epsilon=1$ is a relaxation of (2). Lai \cite{LaiH98} proved the following. \vskip 0.1 in \noindent {\bf Theorem C} (Lai \cite{LaiH98}). Let $G$ be a 2-edge-connected simple graph on $n$ vertices. If $\delta_L(G)\ge \frac{n}{5}-1$, then, for $n$ sufficiently large, either $L(G)$ is Hamiltonian, or (2) is violated and $G$ can be contracted to one of seven specified graphs. \vskip 0.1 in For a 3-edge-connected graph, the Lai's condition in Theorem C can be lowered. \vskip 0.1 in \noindent {\bf Theorem D} (Chen, et al. \cite{CL3}). Let $G$ be a 3-edge-connected simple graph on $n$ vertices and let $\epsilon\ge 1$ be a constant. If $\delta_L(G) \ge \frac{n}{12}-\epsilon,$ then, for $n$ sufficiently large, $L(G)$ is Hamiltonian if and only if $G$ does not have the Petersen graph as a nontrivial contraction. \vskip 0.1 in Adding $\delta(G)\ge 4$ to Theorem D , Li et al. \cite{LiLai2} proved the following.\\ \noindent {\bf Theorem E} (Li, et al. \cite{LiLai2}). Let $G$ be a 3-edge-connected simple graph on $n$ vertices. If $\delta(G)\ge 4$ and if $\delta_L(G)\ge \frac{n-13}{12}$, then either $G\in \SL$ or $G'=P$. \vskip 0.1 in For a 3-edge-connected graph with $\overline{\sigma}_2(G)$ condition, the following was proved:\\ \noindent {\bf Theorem F} (Chen and Lai \cite{CL2}). Let $p>0$ be a given integer and let $G$ be a 3-edge-connected simple graph of order $n>12p(p-1)$. Let $G'$ be the reduction of $G$. If $\overline{\sigma}_2(G)\ge \frac{n}{p}-2$, then either $G\in \C$ or $G'\not =K_1$ with $|V(G')|\le 3p-4$ and $\alpha'(G')\le p$. \vskip 0.1 in In this paper, we prove the following theorem analogous to Theorem F, which unifies Theorems D, E and their improvements given in section 4.\\ \noindent {\bf Theorem 1.1}. Let $G$ be a 3-edge-connected simple graph of order $n$. Let $G'$ be the reduction of $G$. Let $S_0$ be the set of nontrivial vertices in $G'$. Let $Y=V(G')-S_0$. Let $N(p,\epsilon)=\max\{(\epsilon-5)p(p+1), 12p(p+1), (6p+\epsilon-4)p, (\epsilon-1)p(p-1)\}$, where $p>1$ is a given integer and $\epsilon$ is a given real number. If \begin{equation} \delta_L(G) \ge \frac{n}{p}-\epsilon, \end{equation} then, for $n>N(p, \epsilon)$, either $G\in \C$, or $G'\in {\cal Q}_0(3p-5)$ with $\alpha'(G')\le |S_0|\le p$, and $|V(G')|\le 3|S_0|-5\le 3p-5$. Furthermore,\\ \indent (i) if $G'$ has a closed trail containing $S_0$, then $G$ has a dominating closed trail;\\ \indent (ii) if $|S_0|=p$, then $\epsilon\ge 1$ and $|Y|\le (\epsilon-1)p$ and $|V(G')|\le \epsilon p$; \\ \indent (iii) if $\delta(G)\ge 4$, then $|V(G')|\le \max\{|S_0|, 2|S_0|-3\}\le \max\{p, 2p-3\}.$\\ \vskip 0.1 in Combining Theorem 1.1 with the recently proved result on Fan-type condition \cite{Fan}, Theorem F and the prior results in \cite{Cat2, Chen2, CL2}, we have the following: \\ \noindent {\bf Theorem 1.2}. Let $G$ be a 3-edge-connected graph of order $n$. Let $p>1$ be a given integer and let $\epsilon\ge 0$ be a given real number. For any $d(G)\in \Omega(G)$, if $d(G)\ge \frac{n}{p}-\epsilon$, then, for $n$ sufficiently large, $G\in \SL$ if and only if $G'\notin {\cal Q}_0(cp)$, where $c$ depends on $d(G)\in \Omega(G)$ and $c\le 5$ for all $d(G)$. \vskip 0.1 in Thus, a 3-edge-connected graph $G$ of order $n$ with $d(G)\ge \frac{n}{p}-\epsilon$ where $d(G)\in \Omega(G)$ is supereulerian unless $G$ is a graph obtained from a graph $G_p$ in ${\cal Q}_0(cp)$ by replacing some (or all) vertices in $G_p$ with nontrivial subgraphs. From a computational point of view, for given $p$ and $c$, the number of graphs in ${\cal Q}_0(cp)$ is fixed and so it can be determined in a constant time. Like the characterizations of planar graphs, people view that $K_5$ and $K_{3,3}$ are the only non-planar graphs. Thus, in some sense, only a finite number of 3-edge-connected graphs $G$ with $d(G)\ge \frac{n}{p}-\epsilon$ are nonsupereulerian. With Ryj\'{a}\v{c}ek's closure concept on claw-free graphs \cite{Ry}, the techniques used in this paper can be applied to solve degree condition problems of Hamiltonian claw-free graphs. \vskip 0.1 in In section 2, we present some prior results related to Catlin's reduction method, which are the needed mechanism in our proofs in this paper. The proof of Theorem 1.1 is given in section 3. Applications of Theorem 1.1 are presented in section 4. \vskip 0.1 in \section{Prior results related to Catlin's reduction method} For a graph $G$, let $F(G)$ be the minimum number of extra edges that must be added to $G$ to obtain a spanning supergraph having two edge-disjoint spanning trees. For an integer $i>0$, the set of vertices of degree $i$ in $G$ is denoted by $D_i(G)$.\\ \noindent {\bf Theorem G}. Let $G$ be a connected graph and let $G'$ be the reduction of $G$. Then each of the following holds: \vspace{-0.1in} \begin{enumerate} \item[(a)] (Catlin \cite{Catl88}) $G\in \C$ if and only if $G'=K_1$; $G\in \SL$ if and only if $G'\in \SL$; and $G$ has a dominating closed trail if and only if $G'$ has a dominating closed trail containing all the nontrivial vertices of $G'$. \vspace{-0.1in} \item[(b)] (Catlin, et al.\cite{CaHan}) $G'$ is simple and $K_3$-free with $\delta(G')\le 3$, and either $F(G')\ge 3$ or $G'\in \{K_1, K_2, K_{2, t} (t\ge 2)\}$. \vspace{-0.1in} \item[(c)] (Catlin \cite{Ca2}) $F(G')=2|V(G')|-|E(G')|-2$. \end{enumerate} \vskip 0.1 in \noindent {\bf Theorem H}. Let $G$ be a 3-edge-connected graph of order $n$. Let $G'$ be the reduction of $G$. Then each of the following holds: \vspace{-0.1in} \begin{enumerate} \item[(a)] (Chen \cite{C1}). If $n\le 14$, then either $G\in \SL$ or $G'\in \{P, P_{14}\}$. \vspace{-0.1in} \item[(b)] (Chen, et al. \cite{LZ}). If $\alpha'(G)\le 7$, then $G$ is supereulerian if and only if $G'\not \in \{P, P_{14}\}$. If $n\le 15$, then $G$ is supereulerian if and only if $G'\not \in \{P, P_{14}\}$. \end{enumerate} \vskip 0.1in \noindent {\bf Theorem I} (Chen, et al. \cite{CL3}). Let $G$ be a 3-edge-connected graph and let $S \subseteq V(G)$ be a vertex subset such that $|S| \le 12$. Then either $G$ has a closed trail $H$ such that $S \subseteq V(H)$, or $G$ can be contracted to the Petersen graph in such a way that the preimage of each vertex of the Petersen graph contains at least one vertex in $S$. \vskip 0.1 in \noindent {\bf Theorem J} (Li, et al. \cite{LLLZ}). Let $G$ be a 3-edge-connected reduced graph and $G\not \in \SL$.\\ \indent (a) (Lemma 2.6 \cite{LLLZ}). If $F(G)=3$, then $|D_3(G)|=$ the number of edge-cuts of size 3.\\ \indent (b) (Theorem 1.3 \cite{LLLZ}). If $G$ has at most 11 edge-cuts of size 3, then $G=P$. \vskip 0.1 in \noindent {\bf Lemma 2.1}. If $G$ is a reduced graph with $\kappa'(G)\ge 3$ and $G\not \in \SL\cup \{P\}$, then $|D_3(G)|\ge 12$. \begin{proof} Since $G\not \in \SL$ and $\kappa'(G)\ge 3$, $G' \not \in \{K_1, K_2, K_{2,t}\}$. By Theorem G(b), $F(G)\ge 3$. If $F(G)=3$, then since $G\not \in \SL\cup\{P\}$, by Theorem J(b), $G$ has at least 12 edge-cuts of size 3 and so by Theorem J(a) $|D_3(G)|\ge 12$. If $F(G)\ge 4$, then by Theorem G(c), $4\le F(G)=2|V(G)|-|E(G)|-2$, and so $|E(G)|\le 2|V(G)|-6$. Since $2|E(G)|=\sum_{v\in V(G)}d_{G}(v)= \sum_{i=3}i|D_i(G)|$ and $|V(G)|=\sum_{i=3}|D_i(G)|$, \begin{eqnarray*} 2|E(G)|\le 4|V(G)|-12&=&4|D_3(G)|+4|D_4(G)|+\cdots-12;\\ 3|D_3(G)|+4|D_4(G)|+5|D_5(G)|+\cdots &\le & 4|D_3(G)|+4|D_4(G)|+\cdots-12;\\ 12+|D_5(G)|+\cdots &\le& |D_3(G)|. \end{eqnarray*} Thus, $|D_3(G)|\ge 12$. \end{proof} \vskip 0.1 in \section{Proof of Theorem 1.1} We prove the following lemma first. \vskip 0.1 in \noindent {\bf Lemma 3.1}. Let $G$ be a graph of order $n$ with the properties stated in Theorem 1.1. Let $G'\not =K_1$ be the reduction of $G$. For a vertex $v$ in $V(G')$, let $H(v)$ be the preimage of $v$ in $G$. Let $S_0=\{v\in V(G')\ | \ |V(H(v))|>1\}$. Let $Y=V(G')-S_0$. Then, for $n>N(p, \epsilon)$ (as required in Theorem 1.1), $|V(G')|\le 3p-1$. Furthermore, each of the following holds:\\ \indent (a) If $|V(H(v))|>1$ then $|V(H(v))|\ge \frac{n}{p}-\epsilon+1$.\\ \indent (b) $|S_0|\le p$. If $\epsilon<1$, $|S_0|
(\epsilon-5)p(p+1)$, $\frac{n}{p}-\epsilon+3\ge \frac{n}{p_1}-2$. Since $\kappa'(G)\ge 3$, $d(u)\ge 3$ for any $u\in V(G)$. Thus, for any $xy\in E(G)$, by (3) $$ d(x)+d(y)\ge \max\{d(x),d(y)\}+3\ge \delta_L(G)+3\ge \frac{n}{p}-\epsilon+3\ge \frac{n}{p_1}-2.$$ Thus, $\overline{\sigma}_2(G)\ge \frac{n}{p_1}-2$. By $n>12p(p+1)=12p_1(p_1-1)$ and Theorem F, $c\le 3p_1-4=3p-1$. \vskip 0.1 in \noindent (a) Since $|H(v)|>1$, $H(v)$ has an edge $xy$. We may assume that $d(x)\ge d(y)$. By (3) \begin{eqnarray} d(x)=\max\{d(x), d(y)\}\ge \delta_L(G)\ge \frac{n}{p}-\epsilon. \end{eqnarray} Let $i(x)$ be the number of edges in $E(G')$ incident with $x$. Then by (4) \begin{eqnarray} \frac{n}{p}-\epsilon\le d(x)&\le& i(x)+|V(H(v))|-1;\nonumber \\ \frac{n}{p}-\epsilon+1-i(x)&\le& |V(H(v))|. \end{eqnarray} Since $i(x)\le d_{G'}(v)\le c-1\le 3p-2$, by (5) and $n>(6p+\epsilon-4)p$, $|V(H(v))|>3p-1\ge c$. Hence, $H(v)$ has edges that are not incident with any edges in $E(G')$. We may assume $xy$ is such an edge and so $i(x)=0$. Therefore, by (5), $|V(H(v))|\ge \frac{n}{p}-\epsilon+1$. \vskip 0.1 in \noindent (b) Since $\cup_{v\in S_0} V(H(v))\subset V(G)$, $|S_0|(\frac{n}{p}-\epsilon+1)\le n$ and so $|S_0|\le \frac{np}{n-(\epsilon-1)p}$. If $\epsilon<1$, $n-(\epsilon-1)p>n$, and so $|S_0|
(\epsilon-1)p(p-1)$, $|S_0|\le p$. \vskip 0.1 in \noindent (c) Suppose that there are two vertices $y_1$ and $y_2$ in $Y$ such that $y_1y_2\in E(G')$. Since $y_1$ and $y_2$ are trivial vertices in $G'$, $d_G(y_i)=d_{G'}(y_i)\le c-1$ ($i=1,2$). By (3) and $n>(6p+\epsilon-4)p$, $$3p-2\ge c-1\ge \max\{d_G(y_1), d_G(y_2)\}\ge \frac{n}{p}-\epsilon>2(3p-2),$$ a contradiction. Lemma 3.1 is proved. \end{proof} \vskip 0.1 in \begin{proof}[\bf Proof of Theorem 1.1] Let $G'$ be the reduction of $G$. If $G'=K_1$, Theorem 1.1 is true trivially. We may assume that $G'\not =K_1$. Since $\kappa'(G')\ge 3$, $G'\not \in \{K_1, K_2, K_{2,t}\ (t\ge 2)\}$. By Lemma 3.1, $|S_0|\le p$. For each vertex $v\in Y$, $N_{G'}(v)\subseteq S_0$. Thus, for any edge $e$ in $E(G')$, at least one of the ends of $e$ is in $S_0$. Therefore, $\alpha'(G')\le |S_0|\le p$. Since $d_{G'}(v)\ge 3$ for any $v\in Y$, $|E(G')|\ge 3|Y|$. By Theorem G(b), $F(G')\ge 3$. By Theorem G(c) and $|V(G')|=|S_0|+|Y|$, $$3\le F(G')=2|V(G')|-|E(G')|-2\le 2(|S_0|+|Y|)-3|Y|-2.$$ It follows that $|Y|\le 2|S_0|-5$. Therefore, $|V(G')|=|S_0|+|Y|\le 3|S_0|-5\le 3p-5$. \vskip 0.1 in \noindent (i) $G'$ has a closed trail $H$ containing $S_0$. By Lemma 3.1 (c), for any $y\in Y$, $N_{G'}(y)\subseteq S_0$. Thus, $H$ is a dominating closed trail containing all the nontrivial vertices in $S_0$. By Theorem G(a), $G$ has a dominating closed trail. (i) is proved. \vskip 0.1 in \noindent (ii) $|S_0|=p$. By Lemma 3.1 (a), for any $v\in S_0$, $|V(H(v))|\ge \frac{n}{p}-\epsilon +1$. Then $$n=|V(G)|=\sum_{v\in S_0}|V(H(v))|+\sum_{u\in Y}|V(H(u))|\ge |S_0|(\frac{n}{p}-\epsilon +1)+|Y|=n-p\epsilon+p+|Y|.$$ Thus, $|Y|\le (\epsilon-1)p$, and so $|V(G')|=|S_0|+|Y|\le p+(\epsilon-1)p=\epsilon p$. (ii) is proved. \vskip 0.1 in \noindent (iii) $\delta(G)\ge 4$. If $Y=\emptyset$, then $|V(G')|=|S_0|\le p.$ We are done for this case. Next, $Y\not =\emptyset$. By Lemma 3.1(c), for any $u\in Y$, $N_{G'}(u)\subseteq S_0$. Since for every $u\in Y$, $u$ is a trivial vertex in $G'$ and $\delta(G)\ge 4$, $d_{G'}(u)=d_G(u)\ge 4$. Hence, $|E(G')|\ge 4|Y|$. \indent By Theorem G(b), $|E(G')|\le 2|V(G')|-5$. Since $|V(G')|=|Y|+|S_0|$, we have \begin{eqnarray*} 4|Y|&\le & |E(G')|\le 2|V(G')|-5=2(|Y|+|S_0|)-5; \nonumber \\ 2|Y|&\le & 2|S_0|-5. \end{eqnarray*} Since $|Y|$ is an integer, $|Y|\le |S_0|-3$, and so $|V(G')|=|Y|+|S_0|\le 2|S_0|-3\le 2p-3$. \end{proof} \vskip 0.1 in \section{Applications of Theorem 1.1} Using Theorem 1.1, we obtain some new results on Lai's degree conditions for supereulerian graphs and hamiltonian line graphs. For Hamiltonian line graphs, the following theorem is an improvement of Theorem D. \\ \noindent {\bf Theorem 4.1}. Let $G$ be a 3-edge-connected simple graph of order $n$. For any given $\epsilon <\frac{16}{13}$, if $\delta_L(G)\ge \frac{n}{13}-\epsilon$, then, for $n$ sufficiently large, $G$ has a dominating closed trail, i.e., $L(G)$ is Hamiltonian, if and only if $G$ does not have the Petersen graph $P$ as a nontrivial contraction. \begin{proof} This is the special case of Theorem 1.1 with $p=13$ and $\epsilon<\frac{16}{13}$. Let $G'$ be the reduction of $G$. If $G\in \SL$, then we are done. Thus, we may assume that $G\not \in \SL$. Let $S_0$ and $Y$ be the sets defined in Theorem 1.1. Then $|S_0|\le 13$. \vskip 0.1 in \noindent {\bf Case 1}. $|S_0|=13$. By Theorem 1.1(ii), $p=13$ and $\epsilon<\frac{16}{13}$, $|V(G')|\le \epsilon p<\frac{16}{13}\cdot 13=16$. Thus, $13\le |V(G')|\le 15$. By Theorem H(b), $G'=P_{14}$. Then $Y=V(P_{14})-S_0$ and $|Y|=1$. Let $u$ be the only vertex in $Y$. Note that $P_{14}$ is obtained by replacing a vertex in the Petersen graph $P$ with a $K_{2,3}$ such that $P_{14}/K_{2,3}=P$. Let $v_0$ be the contraction image of $K_{2,3}$ in $P$. Then $v_0$ is a non-trivial contraction. If $u$ is a vertex in the $K_{2,3}$ subgraph in $P_{14}$, then $G$ has the Petersen graph $P$ as a nontrivial contraction. We are done for this case. Next, $u$ is a vertex in $V(P_{14})-V(K_{2,3})$. Then $P$ has a closed trail containing $V(P)-\{u\}$. Thus, $G'=P_{14}$ has a dominating closed trail containing $S_0$. By Theorem 1.1(i), $G$ has a dominating closed trail. Theorem 4.1 is proved for Case 1. \vskip 0.1 in \noindent {\bf Case 2}. $|S_0|\le 12$. By Theorem I, one of the following holds: \noindent {\bf Subcase 1}. $G'$ has a closed trail $H$ containing $S_0$. By Lemma 3.1(c) for any $v\in Y=V(G')-S_0$, $N_{G'}(v)\subseteq S_0$ and so the closed trail $H$ is a dominating closed trail containing all the nontrivial vertices of $G'$. By Theorem 1.1(i), $G$ has a dominating closed trail. \vskip 0.1 in \noindent {\bf Subcase 2}. $G'$ can be contracted to $P$ in such a way that the preimage of each vertex of $P$ contains at least one vertex in $S_0$. Then $G$ has $P$ as a nontrivial contraction. \end{proof} \vskip 0.1 in \vskip 0.1 in \begin{picture}(400,80)(0,0) %%% for two P \put(120,50){$G_a$} \put(190,0){Figure 4.1} \put(160,50){\circle*2} %%middle far left \put(160,50){\circle{8}} \put(160,50){\line(1,0){10}} \put(160,50){\line(1,-3){10}} \put(160,50){\line(3,2){30}} \put(170,50){\circle*2} \put(170,50){\circle{8}} \put(170,50){\line(1,0){40}} \put(170,50){\line(3,-2){30}} \put(210,50){\circle*2} \put(210,50){\circle{8}} \put(210,50){\line(2,1){40}} \put(170,20){\circle*2} \put(170,20){\circle{8}} \put(170,20){\line(1,1){10}} \put(170,20){\line(1,0){40}} \put(210,20){\circle*2} %bottom left 2 \put(210,20){\circle{8}} \put(210,20){\line(1,0){20}} \put(180,30){\circle*2} \put(180,30){\circle{8}} \put(180,30){\line(1,3){10}} \put(180,30){\line(3,2){30}} \put(200,30){\circle*2} \put(200,30){\circle{8}} \put(200,30){\line(1,-1){10}} \put(200,30){\line(-1,3){10}} \put(190,60){\circle*2} \put(190,60){\circle{8}} \put(190,60){\line(0,1){10}} \put(190,70){\circle*2} \put(190,70){\line(2,-1){40}} %%second half on the right \put(230,50){\circle*2} \put(230,50){\circle{8}} \put(230,50){\line(1,0){40}} \put(230,50){\line(3,-2){30}} \put(230,20){\circle*2} \put(230,20){\line(1,1){10}} \put(230,20){\line(1,0){40}} \put(270,50){\circle*2} \put(270,50){\line(1,0){10}} \put(280,50){\circle*2} %%far right \put(280,50){\circle{8}} \put(270,20){\circle*2} \put(270,20){\circle{8}} \put(270,20){\line(1,3){10}} \put(240,30){\circle*2} \put(240,30){\circle{8}} \put(240,30){\line(1,3){10}} \put(240,30){\line(3,2){30}} \put(260,30){\circle*2} \put(260,30){\line(1,-1){10}} \put(250,60){\circle*2} \put(250,60){\circle{8}} \put(250,60){\line(0,1){10}} \put(250,60){\line(1,-3){10}} \put(250,70){\circle*2} \put(250,70){\line(3,-2){30}} \end{picture} \vskip 0.1 in \noindent {\bf Remark}. Let $G_a$ be the graph shown in Figure 4.1. Let $S$ be the set of the 13 vertices marked by $\bigodot$. Then $G_a$ does not have a closed trail containing $S$. Let $G$ be the graph obtained from $G_a$ by replacing each vertex with $\bigodot$ by a complete graph $K_{s}$ where $s=\frac{n-5}{13}$. Then $\delta_L(G)\ge s-1=\frac{n-18}{13}$. But $G$ does not have a dominating closed trail. By Theorem A, $L(G)$ is non-Hamiltonian. Thus, $p=13$ in Theorem 4.1 cannot be replaced by $p=14$ and $\epsilon$ cannot be reduced to $\frac{18}{13}$ with $p=13$. \vskip 0.1 in For supereulerian graphs, the following theorem is an improvement of Theorem E.\\ \noindent {\bf Theorem 4.2}. Let $G$ be a 3-edge-connected graph of order $n$ with $\delta(G)\ge 4$. For any given $\epsilon<\frac{4}{3}$, if $\delta_L(G)\ge \frac{n}{12}-\epsilon$ , then, for $n$ sufficiently large, $G\in \SL$ if and only if $G$ does not have the Petersen graph $P$ as a nontrivial contraction. \begin{proof} This is the special case of Theorem 1.1 with $p=12$ and $\epsilon<\frac{4}{3}$. Let $G'$ be the reduction of $G$. If $G'\in \SL$, then by Theorem G(a), graph $G\in \SL$, and we are done. Thus, we may assume that $G'\not \in \SL$ and so $G'\not =K_1$. Since $\kappa'(G)\ge 3$, $\kappa'(G')\ge 3$. Let $S_0$ and $Y$ be the two sets defined in Theorem 1.1. Since $\delta(G)\ge 4$, $D_3(G')\subseteq S_0$. By Theorem 1.1, $|D_3(G')|\le |S_0|\le 12$. By Lemma 2.1, either $G'=P$ or $|D_3(G')|=12.$ \vskip 0.1 in \noindent {\bf Case 1}. $|D_3(G')|=|S_0|=12$. By Theorem 1.1(ii), $|V(G')|\le \epsilon p<\frac{4}{3} \cdot 12=16$, and so $|V(G')|\le 15$. By Theorem H(b), since $G'\not \in \SL$, $G'\in \{P, P_{14}\}$, contrary to $|D_3(G')|=12$. \vskip 0.1 in \noindent {\bf Case 2}. $G'=P$. Since $|D_3(G')|=|S_0|=10=|V(G')|$, each vertex of $G'=P$ is a non-trivial contraction. Theorem 4.2 is proved. \end{proof} \vskip 0.1 in If $\delta(G)\ge 4$ is dropped from Theorem 4.2, then the best Lai's degree condition for 3-edge-connected supereulerian graphs is the following:\\ \noindent {\bf Theorem 4.3}. Let $G$ be a 3-edge-connected simple graph of order $n$. If $\delta_L(G) \ge \frac{n}{8}-\frac{13}{8}$, then, for $n$ sufficiently large, $G\in \SL$ if and only if $G'\not =P$. \begin{proof} This is the special case of Theorem 1.1 with $p=8$ and $\epsilon=\frac{13}{8}$. Using some prior results on 3-edge-connected reduced graphs in \cite{C3}, one can prove Theorem 4.3 in the same way as the proof of Theorem 4.2. The details are omitted here. \end{proof} \vskip 0.1 in \noindent {\bf Remark}. Let $G_1$ be the graph shown in Figure 4.2, where each $\bigodot$ represents a $K_{\frac{n-6}{8}}$ subgraph. Then $G_1$ is a 3-edge-connected graph of order $n$ with $\delta_L(G)\ge \frac{n-6}{8}-1= \frac{n}{8}-\frac{14}{8}$. However, $G_1'=P_{14}$. Thus, the Lai's degree condition in Theorem 4.3 is the best possible. \vskip 0.1 in \begin{picture}(400,85)(0,0) %%P_{14} \put(150,50){\circle*3} %%middle 4 horizontal vertices \put(150,50){\circle{8}} \put(150,50){\line(3,2){30}} \put(150,50){\line(1,0){10}} \put(150,50){\line(1,-3){10}} \put(160,50){\circle*3} \put(200,50){\circle*3} \put(200,50){\circle{8}} \put(200,50){\line(-1,0){40}} \put(200,50){\line(1,0){20}} %%middle line from P to K_{2,3} \put(220,50){\circle*3} %%middle point for K_{2,3} \put(160,20){\circle*3} %%bottom 2 points \put(200,20){\circle*3} \put(200,20){\circle{8}} \put(200,20){\line(-1,0){40}} \put(200,20){\line(4,3){20}} \put(170,30){\circle*3} %%inside 2 low points \put(170,30){\circle{8}} \put(170,30){\line(-1,-1){10}} \put(170,30){\line(1,3){10}} \put(170,30){\line(3,2){30}} \put(190,30){\circle*3} \put(190,30){\circle{8}} \put(190,30){\line(-3,2){30}} \put(190,30){\line(-1,3){10}} \put(190,30){\line(1,-1){10}} \put(180,60){\circle*3} %%inside top points \put(180,70){\circle*3} %%outside top point \put(180,70){\circle{8}} \put(180,70){\line(0,-1){10}} \bezier{360}(180,70)(190,69)(220,65) \put(220,35){\circle*3} %%low inside point of K_{2,3} point \put(220,65){\circle*3} %%top inside point of $K_{2,3} \put(240,45){\circle*3} %%outside two points of K_{2,3} \put(240,45){\circle{8}} \put(240,45){\line(-2,-1){20}} \put(240,45){\line(-4, 1){20}} \put(240,45){\line(-1,1){20}} \put(240,55){\circle*3} \put(240,55){\circle{8}} \put(240,55){\line(-2,1){20}} \put(240,55){\line(-4,-1){20}} \put(240,55){\line(-1,-1){20}} \put(165,0){Figure 4.2} \end{picture} \vskip 0.1 in \begin{thebibliography}{25} \bibitem{BCKV86} A. Benhocine, L. Clark, N. K\"{o}hler and H. J. Veldman, On circuits and pancyclic line graphs, J. Graph Theory 10 (1986), 411--425. \bibitem{BoST77} F. T. Boesch, C. Suffel, and R. Tindell, The spanning subgraphs of Eulerian graphs, J. Graph Theory 1 (1977), 79--84. \bibitem{BoMu76} J. A. Bondy and U. S. R. Murty, ``Graph Theory with Applications", American Elsevier, New York (1976). \bibitem{TSP} S. Boyd, R, Sitters, S. Ster, L. Stougie, The traveling salesman problem on cubic and subcubic graphs, Math. Program., Ser. A (2014) 144: 227--247. \bibitem{Brualdi} R. A. Brualdi, R. F. Shanny, Hamiltonian line graphs. J. Graph Theory 5 (1981), 307--314. \bibitem{Catl88} P. A. Catlin, A reduction method to find spanning Eulerian subgraphs, J. Graph Theory 12 (1988), 29--45. \bibitem{Ca2} P. A. Catlin, Supereulerian graphs, collapsible graphs, and four-cycles, Congressus Numerantium 58 (1987) 233--246. \bibitem{Cat2} P. A. Catlin, Contractions of graphs with non spanning Eulerian subgraphs, Combinatorica 8 (4) (1988), 313--321. \bibitem{CaHan} P. A. Catlin, Z. Han, and H.-J. Lai, Graphs without spanning Eulerian trails, Discrete Math. 160 (1996), 81--91. %\bibitem{Chen1} Z.-H. Chen, A degree condition for spanning Eulerian subgraphs, J. of Graph Theory 17 (1993), 5--21. \bibitem{Chen2} Z.-H. Chen, Supereulerian graphs, independent sets and degree-sum conditions. Discrete Math. 179 (1998), 73--87. \bibitem{CL2} Z.-H. Chen and H.-J. Lai, Collapsible graphs and Matchings, J. of Graph Theory 17 (1993), 597--605. \bibitem{CL3} Z.-H. Chen, H.-J. Lai, X.W. Li, D.Y. Li, J. Z. Mao, Eulerian subgraphs in 3-edge-connected graphs and Hamiltonian line graphs, J. Graph Theory 42 (2003), 308--319. \bibitem{C1} W.-G. Chen and Z.-H. Chen, Spanning Eulerian subgraphs and Catlin's reduced graphs, J. Combinatorial Math. and Combinatorial Computing, (accepted 2014). \bibitem{C3} W.-G. Chen, Z.-H. Chen, M. Lu, Properties of Catlin's reduced graphs and supereulerian graphs, Bulletin of the Institute of Combinatorics and its Applications, (accepted 2015). \bibitem{Fan} W.-G. Chen, Z.-H. Chen, Fan-type conditions for spanning Eulerian subgraphs, Graphs and Combinatorics, (accepted 2015). \bibitem{LZ} Z.-H. Chen, H.-J. Lai and M. Zhang, Spanning trails with bounded independence number or matching number, (submitted 2014). \bibitem{HaNa65} F. Harary and C. St. J. A. Nash-Williams, On Eulerian and Hamiltonian graphs and line graphs, Canad. Math. Bull. 8 (1965), 701--710. \bibitem{LaiH98} H.-J. Lai, Eulerian subgraphs containing given vertices and Hamiltonian line graphs, Discrete Math. 178 (1998), 93--107. \bibitem{Lesniak} L. Lesniak-Foster and J. E. Williamson, On spanning and dominating circuits in graphs, Canad. Math. Bull. 20 (1977), 215--220. \bibitem{LiLai2} X.M. Li, D.X. Li, H.-J. Lai, On 3-edge-connected supereulerian graphs in graph family $C(l,k)$, Discrete Math. 310 (2010), 2455--2459. \bibitem{LLLZ} X. Li, L. Lei, H.-J. Lai, M. Zhang, Supereulerian graphs and the Petersen graph, Acta Mathematica Sinica, English Series, Feb., 2014, Vol. 30, No. 2, pp. 291--304. \bibitem{Pull79} W. R. Pulleyblank, A note on graphs spanned by Eulerian graphs. J. Graph Theory 3 (1979), 309--310. \bibitem{Ry} Z. Ryj\'{a}\v{c}ek, On a closure concept in claw-free graphs, J. Combin. Theory Ser. B 70(1997) 217--224. \bibitem{Veld94} H. J. Veldman, On dominating and spanning circuits in graphs, Discrete Math. 124 (1994), 229--239. \end{thebibliography} \end{document}