Lai's Conditions for Spanning and Dominating Closed Trails

Wei-Guo Chen, Zhi-Hong Chen, Mei Lu

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 Theory 42(2003) 308-319] and in [Discrete Mathematics, 310(2010) 2455-2459].


Keywords


Spanning and dominating closed trails, Hamiltonian line graphs, Collapsible graphs,

Full Text:

PDF