Lan Lei, Xiaoli Wang, Yang Wu, Xiaomin Li
Let $s \geq 0$ and $t \geq 0$ be integers, a graph $G$ is $(s, t)$-supereulerian if for any pair of disjoint edge subsets $X$ and $Y$ with $|Y| \leq s$ and $|X| \leq t, G$ has a spanning eulerian subgraph $H$ with $Y \subseteq E(H)$ and $E(H) \cap X=\varnothing$. In this paper, we study the collapsibility and $(s, t)$-supereulerian properties of $k$-edge-connected graphs, thereby not only extending existing results on collapsible graphs but also further revealing the structural characteristics of $(s, t)$-supereulerian graphs. Let $K_2^c$ denote the edgeless graph on two vertices and $(G-X)_Y$ be the graph obtained by deleting edges in $X$ and subdividing edges in $Y$. We prove the following results. Let $k, s$ and $t$ be given nonnegative integers and $G$ be a graph with $\kappa^{\prime}(G)=k \geq 4$. For any disjoint sets $X, Y \subseteq E(G)$ with $|X|+|Y| \leq k$, each of the following holds.
(i) If $|Y| \leq s$ and $|X| \leq t$, then $G$ is $(s, t)$-supereulerian if and only if $(G-X)_Y$ can not be contracted to $\left\{K_2^c, K_2\right\} \cup\left\{K_{2, p} \mid p\right.$ is odd and $\left.p \leq s\right\}$.
(ii) If $|Y| \leq s$, then either $(G-X)_Y$ is collapsible or $(G-X)_Y$ can be contracted to a member in $\left\{K_2^c, K_2\right\} \cup\left\{K_{2, p} \mid p \leq s\right\}$.
