二色有向图及二色有向自补图的计数与构造

通过构造一种新的群,解决了二色有向图及二色有向自补图的计数问题.获得了有 m 个顶点的一种颜色和 n 个顶点的另一种颜色的二色有向图的计数发生函数B_(m,n)(x)及二色有向自补图的数目分别是 B_(m,n)(x)=Z(S_m*S_n;1+x)和 Z(S_m*S_n;0,2,0,2,…).并构造出 m=n=2的全部76个二色有向图及全部12个二色有向自补图.     

偶自补图的计数

本文应用 De Bruijn 的幂群计数定理和偶图计数结果,解决了偶自补图的计数问题,获得了 m 个顶点独立集与 n 个顶点独立集的所有偶自补图的数目:当 m≠n 时是a_(mn)~C=Z(S_m×S_n;0,2、0,2,…),当 m=n 时是a_(mn)~C=Z([S_n]~S_2;0,2,0,2,…).文中并给出了计数偶自补图数目的实用公式.     

关于有向自补图的构造（Ⅱ）

设Ｄ是有向自补图,Ｖ（Ｄ）＝｛１,２,…,ｎ｝,Ｄ与Ｄｃ之间的同构映射可以表示为Ｖ（Ｄ）上的一个置换σ,记为σ（Ｄ）＝Ｄｃ．若把置换写成不相交轮换的乘积,且σ１和σ２有相同的轮换结构,就有｛Ｄ｜σ１（Ｄ）＝Ｄｃ｝＝｛Ｄ｜σ２（Ｄ）＝Ｄｃ｝．因此,如果对具有不同轮换结构的ｎ阶置换σ,能构造出∪σ｛Ｄ｜σ（Ｄ）＝Ｄｃ｝,就可以构造出所有ｎ阶有向自补图．本文给出了有向自补图的构造方法,并讨论了有向自补图的结构性质．     

阶数不超过8的标定自补图的计数

标定自补图的计数问题是“组合计数”理论中的难题.本文通过构造出的阶数≤8的全部自补图,计算出每一个自补图的自同构群,获得了顶点数分别为4,5和8的标定自补图的数目分别是12,72和112140.     

含悬挂点自补图的递推构造

设Ｇ是ｐ阶自补图，文中讨论了含悬挂顶点的ｐ＋４阶自补图与所有ｐ阶自补图的关系，给出了由ｐ阶自补图构造出ｐ＋４阶含悬挂顶点的自补图的方法及含悬挂点的ｐ＋４阶自补图的数目Ｎ１（ｐ＋４）．     

5个顶点所有136个有向自补图的构造

Ｒｅａｄ在１９６３年就算出５个顶点的有向自补图共有１３６个，但这些图一直未被全部构造出来，本文应用２－重自补图的结果，构造出了１３６个有向自补图．     

2-重自补图和有向自补图的几个性质

本文讨论了2-重自补图和有向自补图的连通性以及2-重自补图的直径,同时以自补置换作为工具研究了当2-重自补图或有向自补图被分成两个连通分支后,这两个连通分支之间的边数与顶点数之间的关系.     

自补图的构造理论与构图

提出并证明了几个自补图的构造命题，探讨了自补图的构造方法。完成了９个点以内的所有自补图构图，并对１２个点的自补图的构图进行了初步探讨。     

正则有向自补图的一种构造方法

现实生活中,计算机网络,交通运输网都可以用图的方法来表示,对网络的构建模型研究,网络的各种参数的研究都可以用关于图的构造方法和图的各种参数来实现,因而对满足某一性质图的构造方法的研究在理论和实际上是有意义的,自补图是一类十分重要的图,它在结构上具有对称性,本文利用的构造的方法,给出了一种构造为2n 1的正则有向自补图的方法。     

关于整正则有向图的补图与联图

把补图与联图这两种二元运算应用于正则有向图,发现无向正则图中的一些定理在有向图中亦成立,使定理的应用范围更加宽广,在此基础上进一步探讨了其成为整谱图的条件,从而得到了构造整谱有向图的新方法,可以用来构造新的整谱有向图.     

有向图的无圈色数的上界

有向图D的无圈色数定义为满足下述要求的D的顶点染色中的最小色数:同色顶点集在D中的导出子图不含有向圈。本文给出D的无圈色数的三种上界,它们改进了已知结果并可以认为是无向图的色数上界在有向图情形的推广。     

关于正则自补图的构造及Kotzig猜想

根据正则自补图的性质，构造出ｋ≤３的全部ｐ＝４ｋ＋１的正同是自补图，并通过这对些图的分析研究，给出了ｋ＝３时Ｋｏｔｚｉｇ猜想的反倒，验证了ＲａｄｈａｋｒｉｓｈｎａｎＮａｉｒ指出的Ｒａｏ构造Ｋｏｔｚｉｇ猜想的反例时出现的一些错误。     

论自补图的周长(Ⅰ)

本文利用自补图的性质和自补图的构造方法证明了阶数 p=5,8、9的所有自补图的周长最大的为 p,最小的为 p—2,它们完全由自补图的度序列和自补图的构造所确定。     

论自补图的构造(Ⅱ)

通过剖析4n阶和4n+1阶自补图之间的关系,应用度序列的方法,以4n阶自补图为基础,给出了构造4n+1阶自补图的递推方法。     

论自补图的周长(Ⅱ)

本文利用自补图的性质和自补图的构构[1]证明阶数p≌0,1(mod4)>9的自补图其周长最大为 p,最小为 p—2.     

有向图的有向圈长分布

阶为v的有向图D的有向圈长分布是序列(c_1,c_2,…,c_v),其中C_i是D中长为i的有向圈的数目。设0≤x_i≤v-i-1,证明了存在v个顶点的有向图D,使D的有向圈长分布为(0,0,x_1,x_2,…,x_(v-3),1),并且给出了具有有向圈长分布为(0,0,x_1,x_2,…,x_(v-3),1)的有向图的最大可能的弧数以及具有有向圈长分布为(0,0,k,k,…,k,k-1,…,3,2,1)(其中1≤k≤v-2)的有向图的最小可能弧数的上界。     

图的色数与其补图边色数的关系

本文对图的点色数与其补图边色数的关系进行了考察.