A Note on Strongly Regular Self-complementary Graphs

K (o) tzig 在强烈常规的自我补足的图上提出了一个问题，也就是说为任何自然数字 k，是否在那里存在强烈常规的自我 -- 其订单是 4k + 的互补的图 1 1 = x2 + y2， x 和 y 是的 4k + 积极整数；什么是在那里做了的最小的数字存在至少二张非同形的强烈常规的自我补足的图。在这份报纸，我们使用二个著名词根与 1 订的 4k + 为强烈常规的自我补足的圆形的图概括存在条件。

自补图的L(2,1)-标号

研究自补图G的L(2,1)-标号问题,证明了自补图的L(2,1)-标号数满足λ(G)≤2Δ。验证了关于一般图的L(2,1)-标号数的猜想λ(G)≤Δ2对于自补图的正确性。

Self-complementary Cayley Graphs of Extraspecial p-groups

This paper constructs several families of self-complementary Cayley graphs of extraspecial p-groups,where p is a prime and congruent to 1 modulo 4.

论自补图的构造(Ⅰ)

本文通过剖析了4n阶自补图的结构,获得了一些关于自补图的重要性质,并且应用这些结果解决了至今悬而未解的问题—4n阶自补图的构造。

有关线图两个性质的讨论

通过介绍线图的内部结构,对线图的连通性以及线图是否为自补图的问题进行了详细的讨论,并得出一些结果.

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

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

论自补图的构造(Ⅱ)

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

完全超紧图

Chia G.L.和Lim C.K.在东南亚第一次图论会议(1983,新加坡)文集的末尾提出六个未解决问题.第五个问题是:设H是自补图,问是否存在自补完全超紧图G,使G~*=H.第六个问题是:设G是完全超紧图.如果G_0与(?)同构,问G是否自补图.本文肯定地回答了第五个问题和否定地回答了第六个问题.

自补图的因子分解

讨论了自补图的１因子分解和２因子分解，利用自补置换证明了自补图有１因子的一个充要条件是阶为４ Ｎ，从最小度角度得到了自补图Ｇ有２因子的一个充分条件是ｍｉｎｖ∈Ｇｄ（ｖ） ≥ ｐ４ （ｐ 是阶） ．

自补图的荫度

文[1]中猜想:对P阶简单图G,有a(G)+a(■)≤1+{P/2}其中■是G的补图,a(G)为G的荫度,{x}为不小于x的最小整数.本文证明对于自补图此猜想是成立的.

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

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

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

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

标定自补图的计数

标定自补图的计数问题是“组合计数”理论中的著名难题,至今毫无进展。本文通过构造出阶≤9的全部自补图,获得了阶数为4,5,8和9的标定自补图的数目分别是12,72,112140和4627224。

自补图的匹配性研究

讨论了自补图的完美匹配的存在性和自补图的最大匹配问题。

拟正则自补图的存在性

本文给出了一类较广的自补图,即拟正则自补图,并讨论了其存在性.

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

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

一种改进的自补图构造方法

现实世界中的交通网络、计算机网络等网络的模型构建都可以用图的构造方法来实现,研究满足某一性质图的构造方法具有十分重要的意义。提出了一种采用自补图标准型矩阵构造自补图的方法,并给出了具体实现算法。结果表明,利用该方法可以解决自补图构造过程中计算量过大的问题。

自补图的性质

构造从G到其补图G的同构映射.得出了自补图及映射的一些性质.

关于G.L.Chia和C.K.Lim的一个问题

G.L.Chia 和 C.K.Lim 提出下列问题:“设 G 是完全超紧图.若 G 是自补完全超紧图,那么 G 是自补图吗?”本文回答了这个问题.

A.Kotzig关于自补图的一个问题

A.Kotzig提出这样一个问题:对于任意正则自补图G,是否存在G的一个自补置换s,s是{1,4,4,...,4}型,定理1否定地回答了这个问题.