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

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

偶自补图的计数

本文应用 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,…).文中并给出了计数偶自补图数目的实用公式.     

具有多个强正则自补图的最小阶数

本文应用两个不同构的13阶强正则自补图,解决了Kotzig在1979年提出尚未解决的问题:“至少存在两个非同构的4k 1个顶点的强正则自补图集中,其最小整数k是什么?”,获得了最小整数k=3,并且否定了Kotzig在这个问题上所获得的结果.     

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

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

论自补图的构造(Ⅱ)

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

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

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

关于标定不相交图并图的树的计数

本文就不相交的标定图的并图G =(V ,E) ,讨论当顶点选自V ,而边不属于E时所能构成树的棵数 ,其中得到的一些结果为文[1 ] [2 ] 等的一些结论的推广 .     

8个顶点的所有10个自补图

本文应用度序列的方法及自补置换圈的有关结果,构造出了8个顶点的全部10个自补图。     

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

通过构造一种新的群,解决了二色有向图及二色有向自补图的计数问题.获得了有 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个二色有向自补图.     

自补图的性质

主要讨论了自补图的结构性质,利用度序列概念及Erdǒs和Gallai得到的度序列的一个结果,得到了自补图的若干新结果,为进一步构造自补图奠定了基础.     

关于几种自补图的直径

本文给出了三种类型的自补图关于直径方面的结果,并从自补图的邻接矩阵给出了自补图直径为2或3的一个充要条件.     

自补图同构的必要条件

本文通过对自补图的4阶和5阶自补子图个数的讨论,给出了两类自补图同构的必要条件。在文章的最后讨论了将这些条件扩充成为自补图同构判断的充要条件的可行性。     

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

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

自补图的构造理论与构图

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

自补图的连通度研究

研究了非平凡自补图,给出了自补图的最大度与最小度的关系,提出了自补图连通度的公式.上述两项结论,以4阶图和5阶图为例,进行了分析讨论.     

2-重自补图论(Ⅰ)——度序列特征

研究了可2-重度序列的基本特征.获得了两个重要结果:(1) 一个2-重图序列是可2-重自补度序列的充要条件;(2) 一个非负整数序列是可2-重自补度序列的充要条件.并在此基础上讨论了构造全部p-维可2-重自补序列的方法和步骤