论文部分内容阅读
设图G=(V(G)，E(G))是一个无向简单连通图，S(∈)V(G)，当连通图G是完全图时，若G-S是平凡图，则称S是G的一个顶点割;当连通图G不是完全图时，若G-S是不连通的，则称S是G的一个顶点割.记G的顶点割集为C(G)={S:S是G的一个顶点割}.i(G)表示G中孤立顶点的个数.定义isc(G)=max{i(G-S)-|S|:S∈C(G)}为图的孤立断裂度，若G的一个顶点割集S*，满足isc(G)=i(G-S*)-|S*|，则称S*是G的一个孤立断裂度集.图G的补图(G)是指与G有相同顶点集V(G)，在(G)中两顶点u，v相邻当且仅当在G中不相邻的图.在这篇文章中，我们研究了几类图的孤立断裂度，本文共分为五章.
第一章主要介绍了本文中将用到的图论的一些基本概念，术语和符号.
第二章研究了顶点数和孤立断裂度为定值的具有最大边数或最小边数的连通图，并且对相应图进行了刻画.主要结果如下:
1设v是不小于2的整数，G是具有最大边数且满足isc(G)=B的v阶连通图，S*为G的一个孤立断裂度集，那么|E(G)|满足下列条件:
(1)若G-S*的所有连通分支都为孤立点，则|E(G)|=(v-B/22)+（v+B/2）（v-B/2）.
(2)若G-S*的所有连通分支至少有一个不是孤立点，则1°当1≤B≤v-4时，|E(G)|=｛（v-B-12）+B+1，2v-4B≥3a+4;(v-2a-B2)+a/2（2v-1-a），2v-4B＜3a+4，其中a=[v-B-2/2].2°当-（v-4）≤B≤0时，|E(G)|=(v-1/2)+（1-B）.3°当B=-（v-2）时，|E(G)|=(v2).
2设v是一个不小于6的整数，G是具有最小边数且满足isc(G)=B的v阶连通图，那么E(G)满足下列条件:|E(G)|=｛v-1，1≤B≤v-4;[v(1-B)/2]，-（v-4）≤B＜-1;v+1+（-1）v， B=-1;v-(-1)v+1/2， B=0;(v2)， B=-（v-2）;v-1.B=v-2.
第三章研究了自补图的孤立断裂度，并且给出了自补图G的孤立断裂度的上下界:-[v-3/2]≤isc(G)≤2.
第四章研究了齿轮图Gn孤立断裂度，并得到了如下结果:
(1)设Gn是一个齿轮图，那么isc(Gn)=1.
(2)设(G)n是齿轮图Gn的补图，那么isc(-(G)n)=1-n.
(3)设Gn是一个齿轮图，那么K2和Gn的笛卡尔积构成的图的孤立断裂度为isc(K2×Gn)=0.
(4)设n≥3和m≥3是正整数，那么Gn和Gm的笛卡尔积构成的图的孤立断裂度为isc(Gn×Gm)=1.
(5)设n≥5是正整数，那么G3，G4，…，Gn的联图的孤立断裂度为isc((G3∨G4)∪(G4∨ G5) U...∪(Gn-i∨ Gn))=-8.
第五章研究了具有m条边的v阶连通图具有的最小孤立断裂度及其相应图的构造方法.并且得出:
设图G是具有m条边的v阶连通图，那么minG∈G(v,m) isc(G)=1-[2m/v]，其中m满足:v-1≤m≤(v2).