一类3p~2阶4度1-正则图

设p为大于3的素数,群G=和H=(其中r(?)1(mod p~2),r~3≡1(mod p~2),3|(p-1))是两类3p~2阶非交换群.通过研究Cayley图的正规性,完成了对G和H的所有4度Cayley图的分类,并得到了一类新的4度1-正则图.     

6度1-正则Cayley图

试图对6度1-正则Cayley图给一个完全分类．利用无核的概念将图自同构群归结到对称群S6的子群．然后根据1-正则图的性质构造出所有可能的具有非交换点稳定子群的无核6度1-正则Cayley图,进一步证明了构造出的图都是有核的,由此给出了这一类图的一个完全分类．     

2p2阶3度Cayley图

Cayley图Cay(G,S)称之为正规的,如果G的右正则表示是Cay(G,S)全自同构群的正规子群。本文决定了2p~2(p为素数)阶群上3度连通Cayley图的正规性,作为该结果的一个应用,对每一个1(?)s(?)5,对2p~2阶3度s-正则Cayley图作了分类。     

三度边正则图的三个无限族

图X称为边正则图，若X的自同构群Aut(X)在X的边集上的作用是正则的．本文考察了三度边正则图与四度Cayley图的关系，给出了一个由四度Cayley图构造三度边正则图的方法，并且构造了边正则图的三个无限族．     

有限素数度弧正则图

如果一个图的全自同构群在其弧集上正则,则称此图为弧正则图.本文刻画素数度的立方自由阶弧正则图,证明任何素数度2倍奇立方自由阶弧正则图都是正规或二部正规Cayley图,且不存在任意素数度4倍奇立方自由阶的弧正则图,推广了一些已知的结果,得到阶为8倍奇平方自由阶素数度弧正则图的分类,并发现新的弧正则图类.此外,基于所得的结果,我们提出一个猜想和有待后续研究的一些问题.     

4p阶三度点传递图

一个图称为点传递图或对称图如果它的自同构群分别在点集或点集有序对上传递.设P为素数,给出了4p阶连通三度点传递图分类(徐明曜等在[Chin.Ann.Math.,2004,25B(4):545-554]中分类了4p阶连通三度对称图).确定了4p阶互不同构的连通三度点传递图的个数f(4p);当P=2,3,5,7时,f(4p)分别为2,4,8,6;当P≥11且4|(p-1)时,f(4p)=5+p-3/2,当P≥11且4|(p-1)时,f(4p)=3+p-3/2.     

4p阶3度点传递图

一个图称为点传递图,如果它的全自同构群在它的顶点集合上作用传递.证明了一个4p(p为素数)阶连通3度点传递图或者是Cayley图,或者同构于下列之一;广义Petersen图P(10,2),正十二面体,Coxeter图,或广义Petersen图P(2p,k),这里k2≡-1(mod 2p).     

2p2阶3度点传递图

一个图称为点传递图,如果它的全自同构群在它的顶点集合上作用传递.本文证明了一个2p～2（p为素数）阶连通3度点传递图或者是Calyley图,或者同构于广义Petersen图P（p～2,t）,这里t～2≡-1（modp～2）.     

无爪3 -正则图的独立数

如果图G的一个集合X中任两个点不相邻, 则称 X 为独立集合. 如果 N[X]=V(G), 则称X是一个控制集合. i(G)(β(G))分别表示所有极大独立集合的最小(最大)基数. γ(G)(Γ(G))表示所有极小控制集合的最小(最大)基数. 在这篇论文中, 作者证明如下结论: (1) 如果 G ∈R 且G 是n阶3 -正则图, 则 γ(G)= i(G), β(G)=n/3. (2) 每个n阶连通无爪3 -正则图 G, 如果 G(G≠ K₄) 且不含诱导子图K₄-e, 则 β(G) =n/3.     

关于3-正则图的路分解

本文讨论了3-正则图的路分解问题,证明了任意的3-正则图都有{P3,P4}分 解,其中Rk指包含k个顶点的路.     

6p2阶的三度半对称图

正则图G 称为G-半对称图, 如果G 的自同构群A := AutG 有一个子群G在G 的边集上传递, 但在其点集上不传递, 特别地, 当G= A时Γ 称为半对称图. 本文旨在考察素数度的(G-)半对称图. 首先给出了素度数的(G-)半对称图的群论刻画, 其次对6p²阶的三度半对称图进行了完全分类, 其中p是奇素数.     

Cayley图的泛因子性质

一个κ-正则图若满足对任意正整数s,1≤s≤κ,均存在一个s-因子或一个2[s/2]因子,则称其有泛因子或偶泛因子性质.本文证明了每个奇度Cayley图是泛因子的,每个偶度Carley图是偶泛因子的.同时证明了二面体群上的每个Cayley图均是泛因子的.     

3-边可染的3-正则图（英文）

若一个连通图的每条边都包含在某一完美匹配中,则称之为匹配覆盖图.设G是一个3-连通图,若去掉G的任意两个顶点后得到的子图仍有完美匹配,则称G是一个brick.而brick的重要性在于它是匹配覆盖图的组成结构因子.3-边可染3-正则5的刻画问题是一个NP-完全问题.本文将此问题规约到3-正则匹配覆盖图上,进而规约到其组成结构因子brick上.我们证明了:一个3-正则图是3-边可染的当且仅当它的所有brick是3-边可染的.     

3—连通正则无爪图的Hamilton圈

本文证明了：任一阶数不超过６ｋ－４的３－连通ｋ－正则无爪图是Ｈａｍｉｔｏｎ的。     

极小正则2-图及其应用

2-图是边的尺寸至多为2的超图,极小正则2-图是不含有真正则因子的正则2-图. 设f₂(n)为所有n个顶点的极小正则2-图的最大度数.给出了极小正则2-图的一个结构性质，并由此证得 f₂(n) =(n+3-i)/3, 其中1≤i≤6, n≥7, i≡n(mod 6),从而解决了范红兵等人提出的一个猜想. 作为在图论中的应用, 可以刻画不可分解因子的正则图, 并给出关于度条件的最好可能的因子存在性定理. 进而, f₂(n)和极小2-图可应用于最初引发这项研究的通用开关盒设计问题.     

关于4p阶3度Cayley图的正规性的一点注记

群G的Cayley图Cay(G,S)称为是正规的,如果G的右正则表示R(G)在Cay(G,S)的全自同构群中正规.设p为奇素数,相关文献决定了4p阶连通3度Cayley图的正规性.本文给出了上述文献的主要结果的一个新的简短的证明.     

一类3-正则图的邻强边染色

对简单图G(V,E),f是从V(G)∪E(G)到{1,2,…,k}的映射,k是自然数,若f满足(1)uv,uw∈E(G),u≠w,f(uv)≠f(uw);(2)uv∈E(G),C(u)≠C(v).则称f是G的一个邻强边染色,最小的k称为邻强边色数,其中C(u)={f(uv)|uv∈E(G)}.给出了一类3-正则重圈图的邻强边色数.     

完全图循环分解成2-正则图

Alspach提出如下猜想:"设n是奇数并且每个m1,m2,…,mh都是大于等于3而小于等于n的整数.若∑mi=n(n-1)/2,则Kn可以分解成圈Cm1,Cm2,…,Cmh."用记号C(mn11 mn22…mn88)表示由ni个mi长圈,i=1,2,…8组成的2-正则图.设Γ={G((2mi)ni…(2m8)n8)|i ∈[1,8]}.研究了循环(Kv,Γ)-分解的构造方法及其存在性问题,并且证明了Alspach猜想的一些特殊情况.     

距离正则图的推广

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

二面体群D_(2n)的4度正规Cayley图

设G是有限群,S是G的不包含单位元1的非空子集．定义群G关于S的 Cayley(有向)图X=Cay(G,S)如下:V(x)=G,E(X)={(g,sg)|g∈G,s∈S}． Cayley图X=Cay(G,S)称为正规的如果R(G)在它的全自同构群中正规．图X称为1-正则的如果它的全自同构群在它的弧集上正则作用．本文对二面体群D2n以Z22 为点稳定子的4度正规Cayley图进行了分类．