关于三类六点七边图的图设计

讨论了三类六点七边图Gi(i=1,2,3)的图设计的存在性问题。     

六点七边图的图设计

六点七边图(不带孤立点的简单图)共有17个图.应用GDD、加权和闭包思想给出了所有六点七边图图设计的构造方法,同时在构造G-HD(7k)(k=3,4,5,6,8)时运用了阿贝尔群的性质,简化了构造过程,并用此方法举例说明如何具体讨论六点七边图图设计的存在性问题,从而得出如下结论:满足v≥k,v(v-1)≡0(mod2e),v-1≡0(modd)且v≥14时,均存在(v,G,1)-GD,其中对v=7,v=8的情况单独讨论.     

一类六点八边图的图设计

设Kv是一个v个点的完全图,G为Kv的一个不含孤立点的简单子图.Kv的一个G-设计,常记为(v,G,1)-GD,是指一个二元组(X,B),其中X为Kv的顶点集,B是Kv的一些子图(亦称为区组)构成的集合,使得每一个区组与G同构,且Kv的任何一条边恰在B的一个区组中出现.文章讨论了一类六点八边图中尚未解决的3个图Gi(i=1,2,3)的图设计存在性问题,并证明了(v,G,1)-GD(i=1,2,3)存在的必要条件v=0,1(mod 16)且≥16也是充分的.从而给出了这类六点八边图图设计存在的完全解.     

一个五点六边图的多部图设计

Kn(g)是一个完全n部图,G为一个不带孤立点的简单图.一个(Kn(g),G)-设计是将Kn(g)划分成边互不相交的子图,使得每一个子图都和G同构.本文讨论了一个五点六边图G的多部图设计存在性问题,证明了(Kn(g),G)-设计存在的充要条件是n(n-1)g2≡0(mod12)且ng≥5.     

图K2,3+e的最优覆盖

设λKv是λ重V点完全图，G为一个无弧立点的有限简单图，λKv的一个G-覆盖设计，记为（v,G,λ）-CD，是指一个对子（X，D），其中X为点集，D为λKv的一些子图（亦称为区组）构成的集合，使得任一区组均与G同构，且任意两个不同点组成的边至少在D的λ个区组中出现，讨论了两类六点七边图Gi=K2,3 e(i=1,2)的最优覆盖的存在性问题，证明了存在（v,Gi,λ）-OCD，i=1,2当且仅当v≥6，除去非最优（但为最大）的C（6，G1，1）=4。     

七点有向θ图的图设计

设Kv是一个v点的有向完全图,G是一个简单有向图,Kv的一个G-设计,记为(v,G,1)-GD,是指一个二元组(X,B),其中X为Kv的点集,B为Kv的一些子图(也称为区组)构成的集合,使得任一子图(区组)与G同构,且Kv的任意两个不同点组成的有向边恰在B的一个区组中出现。研究了七点有向图的图设计的存在性问题。     

一类图的多重多部图设计的存在性

λKn(g)是一个λ重完全n部图,G为一个不带孤立点的简单图.一个(λKn(g),G)-设计是将λKn(g)划分成边互不相交的子图,使得每一个子图都和G同构.对一个五点六边图G的λ重多部图设计的存在性问题进行了研究,证明了(λKn(g),G)-设计存在的充要条件是λn(n-1)g2≡0(mod12),n≥3且ng≥5.     

关于2Kk的图设计

设2Kk表示2个点不相交的k阶完全图,图设计GD(υ,G,1)是1个有序对(V,B),这里V是Kk的点集,B是同构于G的Kk的子图族．给出了图设计GD(υ,2Kk,1)存在的必要条件,讨论了当υ≡1,k^2(mod 2k(k-1))时图设计GD(υ,2Kk,1)的存在性问题,证明了GD(υ,2K4,1)存在的充要条件是υ≡1,16(mod24)．     

关于一类特殊六点八边图的图设计

讨论了一类特殊六点八边图的图设计存在性问题,证明了其存在的充分必要条件,从而给出了这类图设计存在的完全解.     

关于两个六点八边图的图设计

设Kv是一个v个点的完全图,G为Kv的一个不含孤立点的简单子图.Kv的一个G-设计,常记为(v,G,1)-GD,是指一个二元组(X,B),其中X为Kv的顶点集,B是Kv的一些子图(亦称为区组)构成的集合,使得每一个区组与G同构,且Kv的任何一条边恰在B的一个区组中出现.文章讨论了两个六点八边图G1和G2的图设计存在性问题,并证明了(v,Gi,1)-GD(i=1,2)存在的必要条件v≡0,1(mod 16)且vE 16也是充分的.     

七点七边图的图分解

研究了2个七点七边图的图分解, 首先利用带洞图分解给出图分解存在的递归构造, 然后利用差方法构造出递归构造中所需的图分解, 最后给出了图分解的存在谱.     

平面图与对偶原理

该文利用对偶原理创造性地解决了平面图、连通图及对偶图之间的相互关系问题,纠正了长期以来对于平面图及其同构的错误认识,指出平面图必为连通图,平面图本质上是画在同一平面上的顶点、边、面均不相交的连通图。两个平面图的同构指这两个平面图的顶点、边、面之间均有一一对应关系。面是平面图区别于非平面图的本质特征。同构的平面图的对偶图必同构,事实上,平面图的对偶图是唯一的。任意一个平面图都伴有一个隐图,而该隐图实质上是该平面图的对偶图,该隐图可(根据对偶原理)通过D—过程画出。平面图与其对偶图互为对偶。显平面图与其隐对偶图合称为相伴对偶图。     

正则图Cartesian积的线图的秩

设G是一个顶点为n,度为r的正则图,那么它的边为m=1/2nr.G线图是顶点为m,度为（2r-2）,边为1/2nr（r-1）的正则图,本文研究两个正则图或强正则图的Cartesian积图的线图的秩,得到了许多结果,推广了G．J．Davis,G．S．Domke等人的结论．     

Petersen图的一致最优可靠性

本文证明了Petersen图是10点15边图中唯一的一致最优可靠图。     

6长圈带2条悬边的8阶连通图的图设计

构造了所需的带洞图设计, 再结合一些小阶数的图设计的存在性, 得到了关于图Gi (i=1,2,3,4)的图设计(v, Gi ,1)-GD的存在谱, 其中图Gi (i=1,2,3,4)是给6长圈增加2条悬挂边所得的8阶连通图, 且G1, G2, G3, G4互不同构.     

具有最小匹配能量的广义仙人掌图

为了研究具有最小匹配能量的广义仙人掌图的结构,利用一些图形变换对图的匹配能量产生影响的相关方法,得到了具有最小匹配能量的广义仙人掌图的结构:在所有顶点数、边数、块为圈的数目和块为双圈图的数目都固定的广义仙人掌图中,G﹡(n,m,r,s)是匹配能量最小的图;在所有顶点数和边数都固定的广义仙人掌图中,G﹡(n,m,1,(m-n)/2)或G﹡(n,m,0,(m-n+1)/2)是匹配能量最小的图。