Pure Mathematics
Vol.07 No.04(2017), Article ID:21346,5
pages
10.12677/PM.2017.74036
On Criterion of Arc-Transitive Cayley Graphs
Xue Yu
School of Mathematics and Statistics, Yunnan University, Kunming Yunnan
Received: Jun. 22nd, 2017; accepted: Jul. 7th, 2017; published: Jul. 13th, 2017
ABSTRACT
In 1938, R. Fruchet proved that for any given abstract group, there is a graph of it as an automorphism group. Since then, this area, which is about using the groups to study the graphs, opened the curtain. However, extensive research in this area began in 1960, especially in the last 30 years, where a number of important tasks were done. In this paper, we study a branch of graph theory that is, Cayley graph and its decision, especially the arc transitive graph. Firstly, by studying the properties of graph and the exchange of group, we get the main theorem of this paper. Secondly, according to the definition of the normal arc transitive graph and the pushing process of the main conclusion, a judgment condition of the normal arc transitive graph is given.
Keywords:Vertex-Transitive Graph, Arc-Transitive Graph, Cayley Graph, Orbital Graph
关于弧传递Cayley图的判定
于雪
云南大学数学与统计学院,云南 昆明
收稿日期:2017年6月22日;录用日期:2017年7月7日;发布日期:2017年7月13日
摘 要
1938年R. Fruchet证明了对于任意给定的抽象群,都存在一个图以它为自同构群。自此,关于利用群来研究图这一领域,揭开了帷幕。但是,这个领域的广泛研究则是从1960年才真正开始的,尤其是最近30年,在这方面完成了很多重要的工作。本文主要研究了图论的一个分支,即:Cayley图以及它的判定,尤其是弧传递Cayley图的判定。首先,通过研究图的性质以及群的交换性,从而得出本文的主要定理。其次,根据正规弧传递Cayley图的定义以及主要结论的推导过程,得出了一个关于正规弧传递Cayley图的判定条件。
关键词 :边传递图,Cayley图,弧传递图,Orbital图
Copyright © 2017 by author and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY).
http://creativecommons.org/licenses/by/4.0/
1. 引言
本文假设所研究的群是有限群,图是有限的连通的简单的图。在图中,记图
的顶点集、边集、弧集分别为
。若
,且
,使得
则称为
的一个自同构。
的全体自同构对于映射的复合运算构成一个群,称为图
的全自同构群,记其为
。显然有
。若
作用在
的
上是传递的,则分别称
为点传递图、边传递图、弧传递图。特别地,若存在
,且
在
的
上的作用是传递的,则分别称
为G-点传递图、G-边传递图、G-弧传递图。此外,由文献 [1] 知:自同构群
在
的弧集上是传递的,也就是说,
是弧传递图,等价于,
在
的点集上是传递的,且任一点
在
中的点稳定子群
在
的领域
上也是传递的。由此结论,作者对弧传递图的判定,尤其是关于Cayley图的弧传递性产生了兴趣。
设是一个群,
是
的一个不含单位元非空集合,定义图
:点集
,且任意的
,
与
是邻接的当且仅当
,称
是
的关于
的Cayley图,记作
。下面给出本文的主要定理。
定理1.1. 设是一个群,
,则下面的情况是成立的:
1) 若是
的X-边传递Cayley图,则
是弧传递图。
2) 若是交换群,则
是X-弧传递图;若
是非交换群,则
。
进一步地,若图的自同构群
有正规子群与
同构,且在
上是正则的,则称
为
的正规Cayley图。从而可得下面的推论。
推论1.2. 设是
上的X-正规边传递Cayley图,若
,则
是弧传递图。
2. 预备知识
为了证明本文的主要定理,这一节将介绍一些预备的命题和引理。首先,引入Orbital图的相关命题。
设为
上的传递置换群,则
可诱导
上的作用,这个作用的每个轨道,即:
,
,称为
的一个Orbital。每个Orbital
都存在一个对偶Orbital
,即:
。若
,则称
为自对偶的Orbital。称
为广义的Orbital。设
为
在
上的一个Orbital,定义图
:
,
为弧集,称有向图
为
对应的Orbital图,记作
。进一步有,若
为自对偶的,则
为无向图。反之亦然。易知,
为无向图,称为广义Orbital图,通常简记为
。
命题2.1. 记,
。则:
1),
为
的弧传递有向图。
2)为
的弧传递图当且仅当
。
3)为
的边传递图。
4)不是
的弧传递图当且仅当
。
证明:
1) 因为,所以
,则有
。又
,故
可以用
中元素射到
的任意一条弧,故
为
的弧传递有向图。
2) 由1)知:为
的弧传递有向图。又
为无向图当且仅当
,所以
为
的弧传递图当且仅当
。
3) 设,则有
,所以
的边集是
,故
,从而
为
的边传递图。
4) 因为,所以
,因此
不是
的弧传递图。反之亦然。
命题2.2. 设为图,
在
上是传递的,则下面的情况是成立的:
1) 若为G-弧传递图,则
为自对偶Orbital图。
2) 若为G-边传递图,则
为广义的Orbital图。
证明:1) 设,则
为
在
上的一个Orbital,从而
。又因
为G-弧传递图,则
,即:
和
均为自对偶的。因此
与
均为无向图,故
为无向图,即:
为
上的传递置换群
的一个自对偶Orbital图。
2) 因为为G-边传递图,且
在
上是传递的,则
在
上恰有两个轨道,则
,那么
为无向图,所以
为
上的传递置换群
的一个广义的Orbital图。
其次,介绍几个关于Cayley图的引理。
引理2.3. 设是一个群,且
。若
是X-边传递图,则
是X-弧传递图或
在
上有两个Orbital
,并且
。
证明:由文献 [2] 可知,,
是
的任意Orbital到其自对偶Orbital的同构映射。故结论得证。
引理2.4. 设是一个群,且
,
是X-边传递图,若
,对一些
,满足
,则
是X-弧传递图。
证明:在中,
,
因此,中的每一条弧均可表示为
,其中
。又
是X-边传递图,则
,有
。从而
或
。进一步地,
或
,且
,故
是X-弧传递图。
引理2.5. 设,且
在
上是正则的。若
是
的一个Orbital,则
为X-弧传递图,且
,其中
。
证明:因在
上是正则的,则可看作
。又因
,所以
。又
,从而
。
3. 定理的证明
有了前面的预备知识,本节就给出本文主要定理的证明。
定理1.1. 证明1) 因为是X-边传递图,由命题2.2知,
是广义的Orbital图。不妨设
为广义的Orbital,其中
与
是
的对偶Orbital。如果
,由命题2.1知,
是X-弧传递图。现在假设
。若
,
。因为
,则
。设
,则
,满足
,并且
,那么
,
。所以
。又因
且
是正则的,所以
。从而
。因此我们可令
,其中
,由引理2.3知,
。定义一个映射:
,
。则
在中,
在
中,
,
其中是
诱导的内自同构,则
。所以
是
的同构映射。进一步地,
。令
。因
,
,则
且
(因为
)。所以
。进一步地,
且
。
。又因为
,
且
,所以
,
。因此
且
。那么
在
上是传递的。
2) 若是交换群,则
是
的一个同构映射,即:
。所以
,那么
是X-弧传递图。现在设
是非交换群,则
有
,
其中是由
诱导的内自同构,且
。所以
。又
,有
。因此
,从而
。综上,
正规化
,即:
。进一步有
。若
,那么
。因此
,然而
当且仅当
是交换群。这就产生了矛盾,所以
不属于
。因此
。证毕。
下面来证明由定理1.1得出的推论。
推论1.2的证明由文献 [3] 知,,其中
。因为
,所以
。由 [3] Frattini论断知,
,
。设
如定理1.1证明中所定义的,则有
是
-弧传递图。证毕。
注意:1) 在推论1.2中,条件“”不可缺,否则
不一定是
的同构映射。
2) 在推论1.2中,“”不一定成立。
事实上,,
。若
,则
。所以
,那么
正规化
。若
,则
。所以
,那么
不正规化
。综上,
不一定成立。
基金项目
国家自然科学基金《有限群的因子分解与含有传递子群的置换群(k1020531)》;云南省自然科学基金《一些对称图与Cayley图的研究(2013FB001)》;云南大学研究生科研创新基金项目资助(ynuy201688)。
文章引用
于 雪. 关于弧传递Cayley图的判定
On Criterion of Arc-Transitive Cayley Graphs[J]. 理论数学, 2017, 07(04): 277-281. http://dx.doi.org/10.12677/PM.2017.74036
参考文献 (References)
- 1. 徐明曜. 有限群导引(下册)[M]. 北京: 科学出版社, 1999.3.
- 2. Li, C.H. (2006) Finite Edge-Transitive Cayley Graphs and Rotar Cayley Maps. Transactions of the American Mathematical Society, 358, 4605-4635. https://doi.org/10.1090/S0002-9947-06-03900-6
- 3. Godsil, C.D. (1981) On the Full Automorphism Group of a Group. Combinatorial, 1, 243-256. https://doi.org/10.1007/BF02579330