论文部分内容阅读
设G是连通图，S是G的一个顶点子集，当G不是完全图时，若G-S不连通，则称S是G的点断集;当G=Kn时，Kn的任何（n-1）个点组成的集合，亦称为G的点断集.G的所有点断集组成的集合记为C(G).断裂度是图的哈密尔顿性和容错性的一个有效度量，被定义为b(G)=max{ω(G-S)-|S|:S∈C(G)}，其中ω(G-S)表示G-S的分支数.孤立断裂度B(G)定义为B(G)=max{i(G-S)-|S|:S∈C(G)}，其中i(G-S)表示G-S的孤立点数.它是断裂度的改进，能刻画具有相同连通度和相同断裂度的图在连通程度上的差异.本文研究了树的断裂度和一些图的孤立断裂度. 在第一章中，我们给出本文用到的基本的概念和符号.第一节给出本文涉及到的图论的基本概念.第二节给出了断裂度和孤立断裂度的定义和一些研究成果. 本文第二章第一节研究树的断裂度的紧上界，得到了树的最大断裂度公式:设T[n，△]是阶为n(≥2)，最大度为△（≥1）的树组成的集合.那么max T∈T[n，△] b（T）={ n-2[n-1/△] r（n-1/△）≠1n-2[n-1/△]+1 r(n-1/△)=1，其中r（n-1/△）表示n-1/△的余数.第二节研究了树T的断裂度b(T)与它的余树(T)的断裂度b（(T)）的和b(T)+b((T))以及积b（T）b（(T)）的取值范围. 第三章第一节给出了连通图G与其连通补图G的孤立断裂度的关系:-（n-3）≤B(G)+B((G))≤n-3，并证明了对[-(n-3)，n-3]中的任一整数r，都存在连通图G，使得G连通且B(G)+B((G))=r.第二节给出了互补的Hamilton图的孤立断裂度的如上的进一步的关系.第三节确定了Harary图的孤立断裂度.