完全超紧图

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

点传递自补图

图Γ称为点传递自补图,如果Γ的图自同构群AutΓ在顶点集合VΓ作用是传递的,且Γ的补图(Γ)与图Γ是同构的.本文主要研究了通过Cayley同构来构造点自补Cayley图,并证明了内循环群上的这类图必然是循环自补图.     

4K＋1阶强正则自补图的存在唯一性

４ｋ＋１阶强正则自补图的存在唯一性刘象武（哈尔滨师范大学数学系哈尔滨１５００８０）关键词：循环图；强正则自补图；原根ＡＭＳ（１９９１）主题分类：０５Ｅ３０．本文所述的图均指有限无向简单图．本文分别用字母户，庄，人和产表示强正则图的顶点数、正则度、两相...     

A.KOTZIG关于自补图的一个待解问题的反例

本文所用的概念与符号与文献[2]相同,不相同的定义如下。 设G是一个自补图(下称s.c.图),p是G到它的补图G的同构映射,则称p是G的一个自补置换(下简称为s.c.置换)。我们用符号P(G)表示s.c.图G的全体s.c.置换的集合。设p∈P(G),若p是m个轮换的乘积,则记p=p_1p_2…pm,并记pi的长为|pi|。     

自补图中的三角形

该文证明了具有ｐ个顶点的自补图中三角形的数目至多是，当ｐ≡０（Ｍｏｄ４）时为ｐ（ｐ－４）（２ｐ－１）／４８，当ｐ≡１（ｍｏｄ４）时为（ｐ－１）（２ｐ２－７ｐ－３）／４８，并且此二数是最好可能的．     

色多项式的Akiyama—Harary问题

J.Akiyama和F.Harary提出:是否存在非自补图G,使得G与其补图有相同的色多项式,本文给出一个肯定的回答,并证明了:这样的平面图G仅存在有限多个。     

图与其补图谱半径之间的关系

本文我们将图与其补图结合起来，给出了图与其补图的谱半径所必须满足的两个不等式。     

k—一致超图的补图的Laplacian

引入了k-一致超图的补图的概念,并讨论了它的Laplacian与其补图的Laplacian之间的关系。     

森林补图的最小填充

本文研究森林补图的最小填充问题,并给出了森林补图的填充数的表达式.     

图与其补图谱半径之间关系的注记

给出在一般情形和某些限制条件下图及其补图的谱半径的和与积的上界，改进了文［１］的结果。     

On almost self-complementary graphs

A graph is called almost self-complementary if it is isomorphic to one of its almost complements X^c-I, where X^c denotes the complement of X and I a perfect matching (1-factor) in X^c. Almost self-complementary circulant graphs were first studied by Dobson and Šajna [Almost self-complementary circulant graphs, Discrete Math. 278 (2004) 23-44]. In this paper we investigate some of the properties and constructions of general almost self-complementary graphs. In particular, we give necessary and sufficient conditions on the order of an almost self-complementary regular graph, and construct infinite families of almost self-complementary regular graphs, almost self-complementary vertex-transitive graphs, and non-cyclically almost self-complementary circulant graphs.     

强正则自补图的一个注记

Kotzig put forward a question on strongly-regular self-complementary graphs, that is, for any natural number k, whether there exists a strongly-regular self- complementary graph whose order is 4k 1, where 4k 1=x2 y2, x and y are positive integers; what is the minimum number that made there exist at least two non-isomorphic strongly-regular self-complementary graphs. In this paper, we use two famous lemmas to generalize the existential conditions for strongly-regular self-complementary circular graphs with 4k 1 orders.     

On finite self-complementary metacirculants

We prove that the automorphism group of a self-complementary metacirculant is either soluble or has \(\mathrm{A}_5\) as the only insoluble composition factor, extending a result of Li and Praeger which says the automorphism group of a self-complementary circulant is soluble. The proof involves a construction of self-complementary metacirculants which are Cayley graphs and have insoluble automorphism groups. To the best of our knowledge, these are the first examples of self-complementary graphs with this property.     

On the construction of the self-complementary graphs on 12 nodes

We briefly describe how we compiled a catalog of all the 720 self-complementary graphs on 12 nodes. In our first attempt at this compilation one graph was inadvertently omitted. The missing graph was subsequently found by making use of a theoretical formula due to Parthasarathy and Sridharan for counting self-complementary graphs with given partitions.     

Self-Complementary Vertex-Transitive Graphs Need Not be Cayley Graphs

A construction is given of an infinite family of finite self-complementary,vertex-transitive graphs which are not Cayley graphs. To theauthors' knowledge, these are the first known examples of suchgraphs. The nature of the construction was suggested by a generalstudy of the structure of self-complementary, vertex-transitivegraphs. It involves the product action of a wreath product ofpermutation groups. 2000 Mathematics Subject Classification05C25.     

Self-complementary graphs

In this paper a new algorithm is given for the construction of self-complementary graphs, and results concerning structural properties and adjacency matrices of these graphs are presented.     

A class of self-complementary vertex-transitive digraphs

We characterize the class of self-complementary vertex-transitive digraphs on a prime number p of vertices. Using this, we enumerate (i) self-complementary strongly vertex-transitive digraphs on p vertices, (ii) self-complementary vertex-transitive digraphs on p vertices, (iii) self-complementary vertex-transitive graphs on p vertices. Finally it is shown that every self-complementary vertex-transitive digraph on p vertices is either a tournament or a graph.     

On self-complementary vertex-transitive graphs

In this paper we study the problem of determining positive integers n for which there exist self-complementary vertex-transitive graphs of order n. The main aim of this paper is to prove that, for distinct primes p, q, there exist self-complementary vertex-transitive graphs of order pq if and only if p, q Scz.tbnd;1 (mod 4). This provides negative answers to a long-standing open question proposed by Zelinka (1979) and a recent open question proposed by Froncek, Rosa Siran (1996).     

Self-complementary symmetric graphs

The class of self-complementary symmetric graphs is characterized using the classification of finite simple group.     

A class of self-complementary graphs and lower bounds of some ramsey numbers

A method is described of constructing a class of self-complementary graphs, that includes a self-complementary graph, containing no K₅, with 41 vertices and a self-complementary graph, containing no K₇, with 113 vertices. The latter construction gives the improved Ramsey number lower bound r(7, 7) ≥ 114.