几族3-优图

一个图 G中含有的三个结点的导出连通子图的个数 S3( G)在网络可靠性中起着重要作用 .在同点数同边数图类中具有最大 S3( G)的图称为 3-优图 ,它所代表的网络是点故障概率接近 1时的最可靠网络 .本文在已有的结果上进一步证明补图为 a K3∪ b K2 ∪ K1和 a K3-x的图分别是各自图类中唯一的 3-优图 ;补图为 a K3∪ ( b-1 ) K2 ∪ 2 K1和 ( a-1 ) K3∪ b K2 ∪ P3的图是该图类中仅有的两个 3-优图 .     

e≤2(n-2)条件下的3-优图

记S_3(G)为图G所含有的连通的三结点导出子图的个数。图G称为3-优图,若对任何同点同边数的图H有S_3(G)≥S_3(H),3-优图在网络可靠性综合中起着重要作用。本文给出了在e≤2(n-2)条件下3-优图的刻划,其中n为结点数,e为边数,从而解决了文献[1]结论中提出的问题。     

几种复合图生成树个数的一般求法

若一个图能够由某一个或某几个运算作用于不相交的图上而得到，则称该图为复合图．记ｔ（Ｇ）为图Ｇ的生成树个数，Ｈ（Ｇ）为图Ｇ的Ｋｉｒｃｈｈｏｆｆ矩阵，用“ｏ”表示图的某种运算，如“＋”，“×”，“合成”等，本文研究了Ｈ（ＧｏＧ′）与Ｈ（Ｇ），Ｈ（Ｇ′）的特征值关系，给出了ｔ（ＧｏＧ′）的一般性公式，提供了几种复合图生成树个数的一般性公式，提供了几种复合图生成树个数的一般求法，大大推广了［２，３］的结果，同时简化了许多图类生成树个数表达式的求法．     

k——一致最小广播超图研究

本文给出了一个关于k——一致广播函数B_k(n)的公式,它把两类广播函数的某些值统一在一个公式里,由它可得到B(6),B_3(12),B_4(20),B_4(24)的值。另外,我们还用不同的方法分别确定了B_3(19),B_4(17),B_4(18)的值,同时给出一簇k——一致最小广播超图的构造方法,并构造了一些K——一致最小广播超图。