Graphs on which a group of order pq acts edge-transitively

Let F be a finite simple undirected graph with no isolated vertices. Let p, q be prime numbers with p≥q. We complete the classification of the graphs on which a group of order pq acts edge-transitively. The results are the following. If Aut（Г） contains a subgroup G of order pq that acts edge-transitively on F, then F is one of the following graphs： （1） pK1,1; （2） pqK1,1; （3） pgq,1; （4） qKp,1 （p 〉 q）; （5） pCq （q 〉 2）; （6） qCp （p 〉 q）; （7） Cp （p 〉 q = 2）; （8） Cpq; （9） （Zp, C） whereC={±r^μ ｜μ∈Zq} withq〉2, q｜（p-1） and r≠1≡r^q （modp）; （10） Kp,1 （p 〉 q）; （11） a double Cayley graph B（G,C） with C = {1-r^μ ｜ μ ∈ Zq} and r≠1≡r^q （modp）; （12） Kpq,1;or （13） Kp,q.

Super Cyclically Edge Connected Half Vertex Transitive Graphs

Tian and Meng in [Y. Tian and J. Meng, λc -Optimally half vertex transitive graphs with regularity k, Information Processing Letters 109 (2009) 683 - 686] shown that a connected half vertex transitive graph with regularity k and girth g(G) ≥ 6 is cyclically optimal. In this paper, we show that a connected half vertex transitive graph G is super cyclically edge-connected if minimum degree δ(G) ≥ 6 and girth g(G) ≥ 6.

On the Transitivity of the Strong Product of Graphs

Since many large graphs are composed from some existing smaller graphs by using graph operations, say, the Cartesian product, the Lexicographic product and the Strong product. Many properties of such large graphs are closely related to those of the corresponding smaller ones. In this short note, we give some properties of the Strong product of vertex-transitive graphs. In particular, we show that the Strong product of Cayley graphs is still a Cayley graph.

Pentavalent vertex-transitive tiameter two graphs

We classify the family of pentavalent vertex-transitive graphs F with diameter 2. Suppose that the automorphism group of F is transitive on the set of ordered distance 2 vertex pairs. Then we show that either F is distancetransitive or F is one of C8-, K5 K2, C5[K2], 2C4, or K3 K4.

Super Cyclically Edge-connected Vertex-transitive Graphs of Girth at Least 5

A cyclic edge-cut of a graph G is an edge set, the removal of which separates two cycles. If G has a cyclic edge-cut, then it is called cyclically separable. We call a cyclically separable graph super cyclically edge-connected, in short, super-λc, if the removal of any minimum cyclic edge-cut results in a component which is a shortest cycle. In [Zhang, Z., Wang, B.： Super cyclically edge-connected transitive graphs. J. Combin. Optim., 22, 549–562 （2011）], it is proved that a connected vertex-transitive graph is super-λc if G has minimum degree at least 4 and girth at least 6, and the authors also presented a class of nonsuper-λc graphs which have degree 4 and girth 5. In this paper, a characterization of k （k≥4）-regular vertex-transitive nonsuper-λc graphs of girth 5 is given. Using this, we classify all k （k≥4）-regular nonsuper-λc Cayley graphs of girth 5, and construct the first infinite family of nonsuper-λc vertex-transitive non-Cayley graphs.

Regular Factor in Vertex Transitive Graphs

Let G be a fc-regular connected vertex transitive graph. If G is not maximal restricted edge connected, then G has a (k- 1)-factor with components isomorphic to the same vertex transitive graph of order between k and 2k-3. This observation strenghen to some extent the corresponding result obtained by Watkins, which said that fc-regular vertex transitive graph G has a factor with components isomorphic to a vertex transitive graphs if G is not k connected.

On the Stabilizer of the Automorphism Group of a 4-valent Vertex-transitive Graph with Odd-prime-power Order

Abstract Let X be a 4-valent connected vertex-transitive graph with odd-prime-power order p^k (kS1), and let A be the full automorphism group of X. In this paper, we prove that the stabilizer Av of a vertex v in A is a 2-group if p p 5, or a {2,3}-group if p = 5. Furthermore, if p = 5 |Av| is not divisible by 3^2. As a result, we show that any 4-valent connected vertex-transitive graph with odd-prime-power order p^k (kS1) is at most 1-arc-transitive for p p 5 and 2-arc-transitive for p = 5.

Abel群上点传递图中的处处非零3-流

Tutte猜想每个4-边连通图存在处处非零3-流.验证3-流猜想对于定义在Abel群上的点传递图是成立的,这个结果推广了Potocnik等在2005年的研究结果.

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

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

2p^2阶3度点传递图

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

2倍素数幂阶点传递的局部本原图

主要研究了点传递的局部本原图,给出了阶为2倍素数幂的点传递局部本原图的一般性刻画.

点可迁图的限制边连通性

3限制边割是连通图的一个边割,它将此图分离成阶不小于3的连通分支.图G的最小3限制边割所含的边数称为此图的3限制边连通度,记作λ3(G).它以图G的3阶连通点导出子图的余边界的最小基数ξ3(G)为上界.如果λ3(G)=ξ3(G),则称图G是极大3限制边连通的.已知在某种程度上,3限制边连通度较大的网络有较好的可靠性.作者在文中证明如果k正则连通点可迁图的围长至少是5,那么它是是极大3限制边连通的.

点可迁图的顶点划分

设G是k正则连通点可迁图.图G的一个边割S称为限制性边割,如果G-S不含孤立点.最小限制性边割所含的边数λ′称为限制性边连通度.已经证明λ′≤2k-2.等号成立时,称图G是极大限制性边连通的.本文证明了:如果G不是极大限制性边连通的,那么G的顶点集存在一个划分π=(C1,…,Cm),使得由Ch导出的子图同构于一个连通k-1正则点可迁图H,h=1,2,…,m,而且k≤｜H｜≤2k-3.

完全单周期半群的Cayley图的可迁性

刻画了完全单的周期半群G的Cayley图Cay(G,S)的点可迁性,得到了Cay(G,S)是ColAuts(G)-点可迁的、Ends(G)-点可迁的和ColEnds(G)-点可迁的的充分必要条件.

广义Petersen图的弱点传递性

图X称为弱点传递图如果X的自同态幺半群EndX在顶点集V(X)上的作用是传递的 .本文给出了广义Petersen图是二分图的充要条件 ,刻划了奇围长小于 9的广义Petersen图的弱点传递性 ,作为推论给出了所有h ≤ 1 5的弱点传递的广义Pe tersen图P(h ,t) .

图GP(n,t,k)的点传递性

定义图GP(n,t,k)有顶点集V(GP(n,t,k))={ui,vii∈Zn},边集E(GP(n,t,k))={uiui+1,uivi,vivi+t,uivi+ki∈Zn}.讨论了图GP(n,t,k)的自同构映射的性质,给出了它是点传递图的充分条件,进一步分别得到了GP(n,t,k)是Cayley图和拟Cayley图的充分条件.

半群Cayley图的传递性

主要研究了半群Cayley图的传递性.得到了完全单半群的Cayley图的弱点传递性的等价条件,给出了半群的Cayley图是自同构弧传递的充分必要条件,特别地,完全刻画了带的Cayley图的自同构弧传递条件.

交错群A_5的4度连通对称图的分类

一个图Г称为G-对称的(symmetric).如果其同构群Aut(r)的一个子群G在图r的有向孤集(set of ordered pairs of adjacent vertices)上的作用是传递的(transitive).本文主要结果是:设图Г是4度对称图.全自同构群Aut(r)=A_5,则图r是且仅是如下图之一:(1)Г是15个点的完全图K_5的三维覆盖(3-fold cover)图.(2)Г是完全图K_5.

几类非色唯一的连通顶点可迁图

给出了几类非色唯一的连通顶点可迁图,即kKq kKq(k≥2,q≥2)、kCn kCn(k≥2,n≥3)和kRn kRn(k≥2,n∈{3,4,6,12}),其中Kq是具有q个顶点的完全图,Cn是具有n个顶点的回路,Rn是具有n个顶点的最大正则平面图,是两个不相交图的Zykov乘积运算。

关于L.Lovase猜想

本文证明了旋转型的顶点可迁连通图有Harmilton路,从而验证了L.Lovasz猜想在此条件下的正确性。