完全多部图的G-分解,G为有一条对角线的四边形

Kn(g)表示完全n部图Kg ,g ,……g.显然Kn(1)即为n个顶点的完全图Kn.完全多部图Kn(g)的G -分解存在 ,如果Kn(g)是一族同构于G的边不交的所有子图的集合 .本文将研究G为有一条对角线的四边形 (记为Q) ,证明了Kn(g)的G -分解存在的充分必要条件     

完全五部图Kn,n,n,n,n（n≡1,5（mod6））的竞争数

Opsut在1982年给出了任意图G的竞争数小于等于其边团覆盖数的结果.对于完全五部图Kn,n,n, n, n,当n≡1,5(mod6)时,本文首先构造一个极小的边团覆盖并从中得到其边团覆盖数,然后利用边团覆盖和竞争图之间的关系得到了其竞争数的一个新的上界,从而改进了由Opsut给出的完全五部图的上界.     

临界n—边—连通图的几个定理

用λ(G)表示图G的边一连通度,若λ(G)=n且对所有u∈V(G)有λ(G—v)≤n—1则称G为临界n—边一连通图。本文主要结果是:若S是G的一个n—边一割集,C是G—S的一个分支,且V(C)—V(S)≠φ,则存在v_0∈V(G)—V(S)使得λ(G—v_0)=n-1。     

一类极小连通图的Anti-Ramsey 数

给定一个正整数n和一个图族F。Kn的边染色中使得Kn不含有F中任意一个图的多色图的最大的颜色数为F的Anti-Ramsey数,记作AR(n,F)。本文给出了任意一条边都在三角形中的极小连通图的Anti-Ramsey数。     

一个六点七边图的特殊图设计构造

六点七边图(不带孤立点的简单图)共有17个图，在讨论了其余12个图中一个特殊图的图设计存在性问题的基础上，可以用类似的方法解决其余六点七边图(当顶点数为奇数且(7，G1)-GD存在时)的图设计存在性问题。     

m≡0(mod8)时完全二部图Kn,n的循环m-圈分解

研究完全二部图Kn,n的循环m-圈分解的存在性问题．利用差的方法构造完全二部图Kn,n的循环m-圈分解的初始圈．对于m≡0（mod8）且m≥8这种情况,证明当n≡0,m／2,m,3m／2（mod2m）时完全二部图Kn,n存在循环m-圈分解;对于m≡0（mod8）,m≥8且m／4无平方因子这种情况,证明了完全二部图Kn,n存在循环m-圈分解的充分必要条件是n≡0,m／2（modm）．     

关于可行图的几个新结论

设有n个集合X1,X2 ,… ,Xn,一个以X =∪ni=1Xi 为顶点集的图G称为是一个关于集合序列 (X1,X2 ,… ,Xn)的可行图 ,如果对每一个Xi(i=1 ,2 ,… ,n) ,导出子图Gi=G[Xi]是连通的。集合序列 (X1,X2 ,… ,Xn)含最少边数的可行图称为关于 (X1,X2 ,… ,Xn)的最小可行图。将n =3推广至任意的自然数n ,得出了集合序列 (X1,X2 ,… ,Xn)的最小可行图G =∪ni=1Gi,当满足∩ni=1Xi≠Φ时 ,G是关于集合序列 (X1,X2 ,… ,Xn)的最小可行图的一个充分必要条件 ,同时得出了集合序列 (X1,X2 ,… ,Xn)的最小可行图在某种条件下的两个主要结果。     

以-1为特征根的图

图G的邻接矩阵的特征根称为G的特征根.在第二大类和第三大类特征根为-1的图的基础上,刻画了两类新的以-1为特征根的图设G是有n(n≥2)个点的图,以m个点的完全图为其导出子图,如果m,n满足一定的条件,则-1是G一个特征根;设G是有n(＞m)个点的图,如果G的补图Gc同构于一个完全(m-1)部图和一些孤立点的并,则至少是G的n-m重特征根.同时指出了存在其他的以-1为特征根的图.     

最小可行图问题的一个必要条件及总结

设有n个集合X1,X2 ,… ,Xn,一个以X =∪ni =1 Xi 为顶点集的图G称为一个关于集合序列 (X1,X2 ,… ,Xn)的可行图 ,如果对每一个Xi(i=1,2 ,… ,n) ,导出子图Gi=G[Xi]是连通的。那么集合序列 (X1,X2 ,… ,Xn)的含最少边数的可行图称为关于 (X1,X2 ,… ,Xn)的最小可行图。曾得出了n =3时集合序列 (X1,X2 ,X3 )的最小可行图的一个充分必要条件。下面得出了n =4时集合序列 (X1,X2 ,X3 ,X4 )的最小可行图的一个必要条件 ,并用一个例子说明了n =3时的判定最小可行图的充分必要条件 ,不能推广至n≥ 4的情况 ,对最小可行图问题做了总结     

可变样本容量和抽样区间的X和R控制图

最近的理论研究证实了具有可变抽样区间(VSI)的过程控制图和可变样本容量(VSS)控制图比常规控制图(FSSI)能较大地提高控制图的效率。文章假定过程处于统计控制状态的时间t服从负指数分布：f(t)=λe^-λt(≥0)，利用Costa的马氏链方法，设计具有可变样本容量和抽样区间(VSSI)的中位值(X)和极差(R)图。所设计的控制图较之常规控制图能更快地发现过程的变化，从而大大地降低不合格品数。     

P部图的Kirchhoff指标下界

连通图G的两个顶点i和j之间的电阻距离rij定义为通过用单位电阻来代替G中的每条边而构造出的电网络N中的节点i和j之间的有效电阻的阻值．图G的Kirchhoff指标Kf（G）定义为G中所有点对之间的电阻距离之和．得到了n阶p部图G=G（N1,N2,…,Np）（｜Ni｜=ni,i=1,2,…,p）的Kirchhoff指标下界,指出当G为完全p部图时达到下界;并进一步得到,在所有的n阶p部图中,图兰图的Kirchhoff指标最小．     

图是超级限制边连通的一个充分条件

图的超级限制边连通性是度量计算机互连网络可靠性(容错性)的一个重要参数。本文通过考虑图的超级限制边连通性,得到如下结论:若G是n(>7)阶不含三角形的图且对任一对不相邻的顶点x与y有d(x)+d(y) n-1,则G是超级限制边连通的,即super-λ′的。     

最小可行图问题的一个必要条件及总结

设有n个集合X1,X2,…，Xn,一个以X＝∪i=1nXi为顶点集的图G称为一个关于集合序列（X1，X2，…，Xn)的可行图，如果对每一个Xi(i=1,2,…，n)，导出图Gi=G[Xi]是连通的。那么集合序列（X1，X2，…，Xn)的含最少边数的可行图称为关于（X1，X2，…，Xn)的最小可行图。曾得出了n=3时集合序列（X1，X2，X3）的最小可行图的一个充分必要条件。下面得出了n=4时集合序列（X1，X2，X3，X4）的最小可行图的一个必要条件，并用一个例子说明了n=3时的判定最小可行图的充分必要条件，不能推广至n≥4的情况，对最小可行图问题做了总结。     

关于完全图K_n的{P_4,C_4}-分解

讨论了完全图Kn分解成四个顶点的路和圈的存在性,给出完全图Kn存在{P4,C4}-强制分解的充要条件是n≥5且n≠6.以及完全图Kn存在{P4,C4}-分解的充要条件是n≥4.     

关于某些新的非协调图

Graham和Slone引入了协调图的概念。一个具有q条边的图G是协调图 ,如果有一个从G的顶点集到模 q的整数群的一个单射 ,使得当每一条边xy被分配标号f(x) +f(y) (modq)时 ,所产生的边标号是不同的。利用数论的方法证明了一些新的非协调图     

关于某些新的非协调图

Graham和Slone引入了协调图的概念。一个具有q条边的图G是协调图,如果有一个从G的顶点集到模q的整数群的一个单射,使得当每一条边xy被分配标号f(x) f(y)(mod q)时,所产生的边际标号是不同的。利用数论的方法证明了一些新的非协调图。     

关于可行图的几个新结论

设有n个集合X1,X2,…,Xn,一个以X＝∪i=1^nXi为顶点集的图G称为是一个关于集合序列（X1,X2,…,Xn）的可行图,如果对每一个Xi(i=1,2,…,n),导出子图Gi=G[Xi]是连通的。集合序列（X1,X2,…,Xn）含最少边数的可行图称为关于（X1,X2,…,Xn）的最小可行图。将n=3推广至任意的自然数n,得出了集合序列（X1,X2,…,Xn）的最小可行图G=∪i=1^nGi,当满足∩i=1^nXi≠φ时,G是关于集合序列（X1,X2,…Xn）的最小可行图的一个充分必要条件,同时得出了集合序列（X1,X2,…,Xn）的最小可行图在某种条件下的两个主要结果。     

高度不正则图的全着色

图G的正常k全着色是指用k种颜色对G的点和边着色,使相邻或相关联的元素(点或边)着不同色。其中最小的k称为G的全色数,记为χT(G)。设G是一个简单图,υ是G的任意一个顶点,若与υ相邻的顶点的度互不相同,则称G为高度不正则图。对高度不正则图G,文中证明了χT(G)=Δ(G)+1,同时也给出了着色的算法,其中Δ(G)为G的最大度数且Δ(G)≥ 2。     

r-正则图为k-消去图的充分条件

主要研究了正则图中的ｋ－消去图与图的边连通度之间的关系,从而推广了Ｂｏｌｏｂáｓ的结果．其结果如下：Ⅰ设Ｇ是一个ｒ－正则图,｜Ｖ（Ｇ）｜为偶数,λ（Ｇ）≥２．若ｋ为一整数,且ｒ／λ≤ｋ≤ｒ－ｒ／λ,则Ｇ为ｋ－消去图．Ⅱ设ｒ和ｋ为偶数,２≤ｋ≤ｒ,则每一个ｒ－正则图都为ｋ－消去图．Ⅲ设Ｇ为ｒ－正则图,λ（Ｇ）＝λ≥２,且λ＊＝２［λ／２］＋１．若ｒ为奇数,ｋ为偶数,且使得２≤ｋ≤ｒ－ｒ／λ＊,则Ｇ为ｋ－消去图．     

对边幻图猜测的一个证明

令简单图G =(V ,E)是有 p个顶点 q条边的图。假设G的顶点和边由 1 ,2 ,3 ,… ,p + q所标号 ,且 f :V∪E { 1 ,2 ,… ,p + q}是一个双射。如果对所有的边xy ,f(x) + f(y) + f(xy)是常量 ,则称图G是边幻图 (edge-magic)。毛毛虫图是一个树 ,移走它的所有端点产生一个路 (称为T的脊或主干 )。例如 ,路和星图是毛毛虫图。证明了毛毛虫图是边幻图 ,从而证明了顶点不超过 8的树是边幻图。