C2(4,k) 中的强支撑可迹图

设2≤h≤3,l0,k≥0是整数,C_h(l,k)是由h-边连通简单图组成的集合,图G∈C_h(l,k)当且仅当对图G的任意一个二边割或三边割X,图G-X的每个分支都至少有︱V(G)-k︱/l个点.设e=u_1v_1和e'=u_2v_2是图G的两条边.若e≠e',G(e,e')是将图G中的边e=u_1v_1和e'=u_2v_2分别用路u_1v_ev_1和u_2v_e'v_2替换得到的图(其中,v_e,v_e'是不在V(G)中的两个新的点).若e=e',G(e,e')是将图G中的边e=u_1v_1用路u_1v_ev_1替换得到的图,也记作G(e).若对任意的e,e'∈E(G),G(e,e')都有支撑(v_e,v_e')迹,则称图G是强支撑可迹的.作者证明了,若图G∈C_2(4,k)且|V(G)|5k,则要么图G是强支撑可迹图,要么存在e,e'∈E(G),使得G(e,e')可以收缩成一个有限图类F中的图.当k=4时,F被完全确定了.

Strongly Spanning Trailable Graphs in Graph Family C2(4,k)

For integers $h$, $l$ and $k$ with $2\leq h \leq 3$, $l>0$ and $k \geq 0$, let $C_h(l, k)$ denote the family of $h$-edge-connected simple graphs such that $G\in C_h(l, k)$ if and only if for every edge cut $X\subseteq E(G)$ with size $2$ or $3$, each component of $G-X$ has at least $\frac{|V(G)|- k}{l}$ vertices. Suppose that $e=u_1v_1$ and $e''=u_2v_2$ are two edges of $G$. If $e \neq e''$, then $G(e, e'')$ is the graph obtained from $G$ by replacing $e=u_1v_1$ with a path $u_1v_ev_1$ and by replacing $e''=u_2v_2$ with a path $u_2v_{e''}v_2$, where $v_e, v_{e''}$ are two new vertices being not in $V(G)$. If $e = e''$, then $G(e, e'')$, also denoted by $G(e)$, is obtained from $G$ by replacing $e=u_1v_1$ with a path $u_1v_ev_1$. A graph $G$ is strongly spanning trailable if for any $e, e'' \in E(G)$, $G(e, e'')$ has a spanning $(v_e, v_{e''})$-trail. The authors prove that if $G\in C_2(4,k)$ and $|V(G)|> 5k$, either $G$ is strongly spanning trailable, or there exist $e,e''\in E(G)$ such that $G(e,e'')$ is contractible to a member in a finite family $\mathcal{F}$. When $k=4$, $\mathcal{F}$ is determined.