强正则图的一些性质

文[3]给出了强正则图的概念及有关性质,本文在此基地上利用图的谱性质,得到了强正则图的又一些性质。     

非正则图的最大特征值

通过对图的最大特征分量与顶点度之间的关系的刻画,得到了图的谱半径与参数最大度和次大度之间的不等关系,进而获得了简单连通非正则图的谱半径的若干上界.     

连通度与强正则图的2—可扩性

本文证明了所有具有偶顶点数的强正则图是1—可扩的,如果强正则图G具有偶顶点数和参数(v,k,α,β),并且G的圈边连通度至少为3k—3测G是2—可扩的.     

正则图的变换图的谱

设G是一个图,类似全图的定义,可以定义G的8种变换图.如果G是正则图,那么图G的变换图的谱都可以由图G的谱计算得到.     

一类2级一般强正则图

作为强正则图的一种新推广,p级一般强正则图是使得任意两个邻接的顶点和任意两个不邻接的顶点的公共邻接点数都有p种不同取值的非空k-正则图.对于参数为(n,k;a₁,a₂;c₁,c₂)的2级一般强正则图中任一顶点,如果与这个顶点邻接且有a_i (i=1,2)个公共邻接点或者与这个顶点不邻接且有c₁ (i=1,2)个公共邻接点的顶点数与该点的选取无关,则称这个2级一般强正则图为自由的.本文研究了参数为(n,k;k-1,a₂;k-1,c₂)的2级一般强正则图,得到一类自由的2级一般强正则图存在的充要条件.     

距离正则图的推广

本文研究了直径为d(Γ) ≥ 2的距离正则图Γ的补图.利用Γ的交叉数分别证明了当d=2时,Γ的补图式强正则;当d ≥ 3时,Γ的补图是广义强正则.将文献[2]中的距离正则图Grassmann图、对偶极图、Hamming图推广到它们的补图,从而得到广义强正则图.     

关于5-正则图的强协调性

构造了若干个 5 -正则图的强协调值 ,从而证明它们都是强协调的     

图的强收缩核与图的强自同态幺半群的正则性

本文研究图及其强自同态幺半群．首先刻画了图的强自同态幺半群的正则元，然后给出了此幺半群正则的充要条件．这推广了［１］和［２］中关于有限图的强自同态幺半群正则的结果．     

图的强化缩核与图的强自同态幺半群的正则性

本文研究图及其强自同态幺半群，首先刻画了图的强自同态幺半群的正则元，然后给出了此幺半群正则的充要条件，这推广了（１）和（２）中关于有限图的强自同态幺半群正则的结果。     

变换图的正则性和谱半径

在前人对八种变换图研究的基础上,探讨了变换后满足正则性的原图的性质,得到了如下结果:G~( )及G~(---)是正则图当且仅当G是正则图;G~( -)和G~(-- )为正则图的充要条件是G为C_n、K_(2,n-2)或K_4;G~( - )和G~(- -)是正则图当且仅当G为C_5、K_7、K_2、K_(3,3)或G_0;G~(- )和G~( --)是正则的当且仅当G是(n-1)/2-正则图．同时还讨论了变换图的谱半径上界,并对这些上界进行了估计．     

Strongly Regular Semi-Cayley Graphs

We consider strongly regular graphs = (V, E) on an even number, say 2n, of vertices which admit an automorphism group G of order n which has two orbits on V. Such graphs will be called strongly regular semi-Cayley graphs. For instance, the Petersen graph, the Hoffman–Singleton graph, and the triangular graphs T(q) with q 5 mod 8 provide examples which cannot be obtained as Cayley graphs. We give a representation of strongly regular semi-Cayley graphs in terms of suitable triples of elements in the group ring Z G. By applying characters of G, this approach allows us to obtain interesting nonexistence results if G is Abelian, in particular, if G is cyclic. For instance, if G is cyclic and n is odd, then all examples must have parameters of the form 2n = 4s ² + 4s + 2, k = 2s ² + s, = s ² – 1, and = s ²; examples are known only for s = 1, 2, and 4 (together with a noncyclic example for s = 3). We also apply our results to obtain new conditions for the existence of strongly regular Cayley graphs on an even number of vertices when the underlying group H has an Abelian normal subgroup of index 2. In particular, we show the nonexistence of nontrivial strongly regular Cayley graphs over dihedral and generalized quaternion groups, as well as over two series of non-Abelian 2-groups. Up to now these have been the only general nonexistence results for strongly regular Cayley graphs over non-Abelian groups; only the first of these cases was previously known.     

Cyclotomy and Strongly Regular Graphs

We consider strongly regular graphs defined on a finite field by taking the union of some cyclotomic classes as difference set. Several new examples are found.     

Distance-Regular Graphs with Strongly Regular Subconstituents

In [3] Cameron et al. classified strongly regular graphs with strongly regular subconstituents. Here we prove a theorem which implies that distance-regular graphs with strongly regular subconstituents are precisely the Taylor graphs and graphs with a ₁ = 0 and a _i {0,1} for i = 2,...,d.     

Spreads in Strongly Regular Graphs

A spread of a strongly regular graph is a partitionof the vertex set into cliques that meet Delsarte's bound (alsocalled Hoffman's bound). Such spreads give rise to coloringsmeeting Hoffman's lower bound for the chromatic number and tocertain imprimitive three-class association schemes. These correspondenceslead to conditions for existence. Most examples come from spreadsand fans in (partial) geometries. We give other examples, includinga spread in the McLaughlin graph. For strongly regular graphsrelated to regular two-graphs, spreads give lower bounds forthe number of non-isomorphic strongly regular graphs in the switchingclass of the regular two-graph.     

On the Cayley Graphs of Brandt Semigroups

In this article, the Cayley graphs of Brandt semigroups are investigated. The basic structures and properties of this kind of Cayley graphs are given, and a necessary and sufficient condition is given for the components of Cayley graphs of Brandt semigroups to be strongly regular. As an application, the generalized Petersen graph and k-partite graph, which cannot be obtained from the Cayley graphs of groups, can be constructed as a component of the Cayley graphs of Brandt semigroups.     

Binary Codes of Strongly Regular Graphs

For strongly regular graphs ith adjacency matrix A, we look at the binary codes generated by A and A + I. We determine these codes for some families of graphs, e pay attention to the relation beteen the codes of switching equivalent graphs and, ith the exception of two parameter sets, we generate by computer the codes of all knon strongly regular graphs on fewer than 45 vertices.     

简单完整正则平面图

对简单完整正则平面图的特性和结构进行了分析和讨论 ,找出了简单完整正则平面图的可能的种类 .此外 ,对各种简单完整正则平面图的色数进行了求解 ,并用不同的方法给出了各个简单完整正则平面图的作色方案 .     

Constructions of Strongly Regular Cayley Graphs Using Even Index Gauss Sums

In this paper, generalizing the result in [9], I construct strongly regular Cayley graphs by using union of cyclotomic classes of and Gauss sums of index w, where is even. In particular, we obtain three infinite families of strongly regular graphs with new parameters.