论文部分内容阅读
本论文主要讨论了图论中的n-因子-临界性以及n-可扩性。在第一章中,我们证明了如下结论:设图G是阶为p的简单连通图,n为小于p的非负整数并且p≡n(mod2),如果对G中任意一对距离为2的点u,v都有d(u)+d(v)≥p+n-1,则图G是n-因子-临界图。这一结论是对Favaron[2]中一结果的改进,由它我们还得到了一些有趣的推论。在第二章中,我们证明了关于n-因子-临界性的两命题的条件是等价的:设图G是p阶k-连通图,独立数为α(G),且0≤n≤k,则下述两条件等价:(1)α(G)≤k-n+1(2)存在自然数s满足2≤s≤k使得对于G中任意s个点的独立集S都有|N(S)|+k≥p+n-1.由于每一个偶阶哈密尔顿连通图是O-因子-临界的,我们在最后一章中我们主要涉及哈密尔顿连通性,利用一个重要的引理,我们得到了一些新结果,并且改进了或推广了一些经典结论。同时我们构造了一些极图来说明这些改进的结果是最好的。