论文部分内容阅读
本文主要研究强支撑可迹图的相关内容.设e=u1v1和e=u2v2是图G的两条边.若e≠e，G(e，e)是将图G中的边e=u1v1和e=u2v2分别用路u1vev1和u2vev2替换得到的图(其中，ve，ve是不在V(G)中的两个新的点）.若e=e，G(e，e)是将图G中的边e=u1v1用路u1vev1替换得到的图，也记作G(e).若对任意的e，e∈E(G)，G(e，e)都有支撑(ve，ve)-迹，则称图G是强支撑可迹图.根据强支撑可迹图的定义知强支撑可迹图是一类特殊的超欧拉图.Shao说明了只要确定图G的核是强支撑可迹图就能确定图G的线图是哈密尔顿连通的.由于强支撑可迹图问题有着如此广泛的应用，因而对其理论进行深入的分析研究具有非常重要的实际意义的.本文的主要结论分为两部分: 一、刻画了图类C2(4，k)中的强支撑可迹图. 设2≤h≤3，l＞0，k≥0是整数，Ch（l，k）是由h-边连通简单图组成的集合.图G∈Ch（l，k）当且仅当对于图G的任意一个二边割或三边割X，图G-X的每个分支都至少有(|V(G)|-k）/l个点.证明了，若图G∈C2(4，尼)且|V(G)|＞5k，则要么图G是强支撑可迹图，要么存在e，e∈E(G)，使得G(e,e)可以收缩成一个有限图类F中的图.当k=4时，F被完全确定了. 二、证明了非增多重图度序列有强支撑可迹图实现的充要条件，并利用它给出了非增多重图度序列有哈密尔顿连通线图实现的充分条件. 对于序列d=(d1，d2，…，dn)，如果存在一个多重图G的度序列恰好是d，则称d是多重图度序列，图G称作是d的一个实现.对于多重图度序列d，如果d的一个多重图实现是强支撑可迹图，则称d是强支撑可迹多重图度序列.对于多重图度序列d，如果d的一个多重图实现G的线图是哈密尔顿连通图，则称d是哈密尔顿连通线图多重图度序列.证明了非增多重图度序列d=(d1，d2，…，dn)是强支撑可迹多重图度序列的充要条件:或者n=1和d1=0，或者n≥2和dn≥3.应用此结论得到:对于一个非增多重图度序列d=(d1，d2，…，dn)，如果n≥2和dn≥3.则d是哈密尔顿连通线图多重图度序列. 本文分四章:第一章介绍了超欧拉图和强支撑可迹图的相关研究背景、基本概念等等;第二章中刻画了图类C2(4，k)中的强支撑可迹图;第三章证明了非增多重图度序列有强支撑可迹图实现的充要条件.第四章对全文进行了总结，并对有待于进一步研究的问题进行了展望.