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

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

设2≤h≤3,l>0,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被完全确定了.

For integers h, l and k with 2 ≤h≤3, l〉 0 and k≥0, let Ch（l,k） denote the family of h-edge-connected simple graphs such that G ∈ Ch（l,k） if and only if for every edge cut X？E（G） with size 2 or 3, each component of G-X has at least︱V（G）-k︱/l vertices.Suppose that e = u1v1 and e＇= u2v2 are two edges of G. If e ≠ e＇, then G（e,e＇） is the graph obtained from G by replacing e =u1v1 with a path u1 vev1 and by replacing e＇= u2v2 with a path u2 ve＇v2, where ve,ve＇ 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 = u1v1 with a path u1 vev1.A graph G is strongly spanning trailable if for any e,e＇ ∈ E（G）,G（e,e＇） has a spanning（ve,ve＇）-trail. The authors prove that if G∈C2（4, k） and ｜V（G）｜）〉 5 k, either G is strongly spanning trailable, or there exist e,e＇ ∈ E（G） such that G（e,e＇） is contractible to a member in a finite family F. When k=4,F is determined.