Publications

On $(s,t)$-supereulerian graphs with linear degree bounds.

Faculty Author(s): Zhan, Mingquan
Student Author(s): -
Department: MATH
Publication: Discrete Mathematics
Year: 2021
Abstract: For integers $s\ge 0$ and $t\ge 0$, a graph $G$ is $(s,t)$-supereulerian if, for any disjoint edge sets $X,Y\subseteq E(G)$ with $|X|\le s$ and $|Y|\le t$, $G$ has a spanning closed trail that contains $X$ and avoids $Y$. Let $\delta(G)$ and $\kappa'(G)$ be the minimum degree and the edge connectivity of a graph $G$, respectively. Settling an open problem of D. Bauer posed in [``On Hamiltonian cycles in line graphs'', Stevens Research Report PAM No. 8501, Stevens Inst. Tech., Hoboken, NJ.; per bibliography; Congr. Numer. {\bf 49} (1985), 11--18; [msn] MR0830724 [/msn]], P.~A. Catlin [J. Graph Theory {\bf 12} (1988), no.~1, 29--44; [msn] MR0928734 [/msn]] proved the following theorem: \par Theorem 1. Let $G$ be a simple graph on $n$ vertices with $\kappa'(G)\ge 2$. If $\delta(G)\ge n/5-1$, then when $n$ is sufficiently large, $G$ is $(0,0)$-supereulerian, or $G$ can be contracted to a $K_{2,3}$. \par In the present paper, the authors consider this problem for any nonnegative integers $s$ and $t$, and prove the following theorem: \par Theorem 2. For any nonnegative integers $s$ and $t$, and any real numbers $a$ and $b$ with $0 Link: On $(s,t)$-supereulerian graphs with linear degree bounds.