【作者】 周书明；

【导师】 刘展鸿； 熊黎明；

【作者基本信息】 江西师范大学 ， 应用数学， 2002， 硕士

【摘要】 本论文主要讨论了图论中的n-因子-临界性以及n-可扩性。 在第一章中，我们证明了如下结论： 设图G是阶为p的简单连通图，n为小于p的非负整数并且p≡n(mod 2)，如果对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-因子-临界的，我们在最后一章中我们主要涉及哈密尔顿连通性，利用一个重要的引理，我们得到了一些新结果，并且改进了或推广了一些经典结论。同时我们构造了一些极图来说明这些改进的结果是最好的。更多还原

【Abstract】 This thesis mainly concentrates on n - factor - criticality and n - extendablity in graph theory,and we will find the first two chapters that contain more or less independent topics within this research field.In the first chapter we prove the following result:Let G be a graph of order p with p=n(mod 2) and n<p,if d(u) + d(v)p + n -1 for every pair of nonadjacent vertices u,v of G with d (u,v) = 2,then G is n -factor -critical.By this theory we obtain some interesting corollaries,which include n - extendablity.In the second chapter,we can prove the conditions of two propositions involving n -factor- criticality are equivalent:Let G be a k - connected graph of order p,connectivity k,independence number a (G) and 0n<k,then the following two conditions are equivalent:(l)a(G)<k-n + l(2)there exist a integer s with 2<s<k such that I N( S ) I + k>p + n - 1 holds for every independent set S of s vertices in G.In the last chapter,we focus on hamilton - connectivity for every hamilton - connected graph with even order is 0 - factor - critical. Before the discussion of this chapter,we prove the following useful lemma:Let G be a graph of order n,then the inequality d(u) + d(v) + d(w) - N(u) N(v)N(w)>3NC-n+3 holds for any independent set (u,v,w)in V(G).Combination of this lemma and the hamilton - connectivity involving neighborhood intersection obtains and improves or generalizes a series of classical results involving hamilton - connectivity,at the same time,we construct some extremal graphs to show the improved results to be the best possible ones. As for hamiltonicity,we omit the similar discussion.更多还原