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

作     者：余爱梅 马仁森 王可可 孔将旭 YU Aimei;MA Rensen;WANG Keke;KONG Jiangxu

作者机构：北京交通大学数学系北京100044 Department of Mathematics Embry-Riddle Aeronautical University 中国计量大学理学院杭州310018 

出 版 物：《数学年刊（A辑）》 (Chinese Annals of Mathematics)

年 卷 期：2018年第39卷第1期

页      面：53-62页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：国家自然科学基金(No.11371193 No.11701541) 北京交通大学基本科研业务费(No.2015JB M107) 北京高等学校青年英才计划项目(No.YETP0573) 高等学校学科创新引智计划(No.B16002) 浙江省自然科学基金(No.LQ17A010005)的资助 

主　　题：强支撑可迹图 可折叠图 简化图 

摘      要：设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被完全确定了.