2p2阶3度点传递图

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

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~2阶4度半传递图

如果图X的全自同构群Aut(X)作用在其顶点集V(X)和边集E(X)上都是传递的,但作用在弧集Arc(X)上非传递,则称X是半传递图.研究了4p~2(p3且p≡-1(mod4))阶4度半传递图,确定了4p~2阶4度半传递图的连通性及其自同构群的阶.     

2p2阶3度Cayley图

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

一类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-正则图.     

p~2阶弧传递循环图的正规性条件

群G关于S的有向Cayley图X=Cay(G,S)称为pk阶有向循环图,若G是pk阶循环群.利用有限群论和图论的较深刻的结果,对p2阶弧传递(有向)循环图的正规性条件进行了讨论,证明了任一p2阶弧传递(有向)循环图是正规的当且仅当(|Aut(G,S)|,p)=1.     

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

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

非交换单群上三度点传递双凯莱图

如果一个图Γ含有一个自同构群G使得它在顶点集V(Γ)上作用半正则且恰好有两个轨道,则称图r是群G上的双凯莱图.进一步的,如果G在全自同构群Aut(Γ)中正规,我们就称这个双凯莱图是群G上的正规双凯莱图.本文中,我们证明了绝大多数非交换单群G上的三度点传递双凯莱图都是该群上的正规双凯莱图.     

3p阶亚循环群的连通4度Cayley图

研究3p阶(p是大于3的素数)亚循环群的连通4度Cayley图.主要决定了其全自同构群的结构,并由此得到这类图的CI性、正规性和弧传递性.用到单群分类定理.     

点传递自补图

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

连通的顶点可迁图的色唯一性

本文给出从一个已知的顶点可迁的非色唯一图出发,构造无穷多个顶点可迁的非色唯一图的一种方法,据此给出若干类无穷多个连通的顶点可迁,但不是色唯一的图簇,从而进一步否定地回答了Chia在[1]中提出的问题.     

Non-Cayley Vertex-Transitive Graphs of Order Twice the Product of Two Odd Primes

For a positive integer n, does there exist a vertex-transitive graph Γ on n vertices which is not a Cayley graph, or, equivalently, a graph Γ on n vertices such that Aut Γ is transitive on vertices but none of its subgroups are regular on vertices? Previous work (by Alspach and Parsons, Frucht, Graver and Watkins, Marusic and Scapellato, and McKay and the second author) has produced answers to this question if n is prime, or divisible by the square of some prime, or if n is the product of two distinct primes. In this paper we consider the simplest unresolved case for even integers, namely for integers of the form n = 2pq, where 2 < q < p, and p and q are primes. We give a new construction of an infinite family of vertex-transitive graphs on 2pq vertices which are not Cayley graphs in the case where p ≡ 1 (mod q). Further, if p ? 1 (mod q), p ≡ q ≡ 3(mod 4), and if every vertex-transitive graph of order pq is a Cayley graph, then it is shown that, either 2pq = 66, or every vertex-transitive graph of order 2pq admitting a transitive imprimitive group of automorphisms is a Cayley graph.     

Vertex-Transitive Non-Cayley Graphs with Arbitrarily Large Vertex-Stabilizer

A construction is given for an infinite family {_n} of finite vertex-transitive non-Cayley graphs of fixed valency with the property that the order of the vertex-stabilizer in the smallest vertex-transitive group of automorphisms of _n is a strictly increasing function ofn . For each n the graph is 4-valent and arc-transitive, with automorphism group a symmetric group of large prime degree . The construction uses Sierpinski's gasket to produce generating permutations for the vertex-stabilizer (a large 2-group).     

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

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

Enumerating Planar Locally Finite Cayley Graphs

We characterize the set of planar locally finite Cayley graphs, and give a finite representation of these graphs by a special kind of finite state automata called labeling schemes. As a result, we are able to enumerate and describe all planar locally finite Cayley graphs of a given degree. This analysis allows us to solve the problem of decision of the locally finite planarity for a word-problem-decidable presentation.Mathematics Subject Classiffications (2000). 20F05, 20F10, 20F65, 05C25     

一类16p阶群的三度Cayley图的正规性

有限群G的一个Cayley图X=Cay(G,S)称为正规的,如果右乘变换群R(G)在AutX中正规.研究了一类16p阶群G=〈a,b|a^(8p)=b(8p)=b²=1,a2=1,a^b=ab=a^(4p-1)〉的3度无向连通Cayley图的正规性,其中p为奇素数,并得到该群的正规与非正规的Cayley图