單群的點(diǎn)傳遞圖的GI-性質(zhì)

陳 靜, 曲斯瑤

(1. 福州大學(xué)離散數(shù)學(xué)與理論計算機(jī)科學(xué)研究中心， 福建 福州　350003; 2. 湖南第一師范學(xué)院數(shù)學(xué)與計算科學(xué)學(xué)院， 湖南 長沙　410205)

?

單群的點(diǎn)傳遞圖的GI-性質(zhì)

陳 靜1, 2, 曲斯瑤2

(1. 福州大學(xué)離散數(shù)學(xué)與理論計算機(jī)科學(xué)研究中心， 福建 福州350003; 2. 湖南第一師范學(xué)院數(shù)學(xué)與計算科學(xué)學(xué)院， 湖南 長沙410205)

針對點(diǎn)傳遞圖的同構(gòu)問題， 類似于Babai關(guān)于Cayley圖為CI圖的充分必要條件， 給出了點(diǎn)傳遞圖為GI-圖的判別準(zhǔn)則， 并研究了單群的點(diǎn)傳遞圖的GI-性質(zhì).

點(diǎn)傳遞圖； 單群； 陪集圖； GI-圖

0　引言

設(shè)Γ是一個圖, V(Γ)、 E(Γ)、Arc(Γ)以及Aut(Γ)分別表示圖Γ的頂點(diǎn)集、 邊集、 弧集以及全自同構(gòu)群. 令G是Aut(Γ)的一個子群, 如果G傳遞地作用在圖Γ的頂點(diǎn)集、 邊集或弧集上, 則分別稱圖Γ是G-點(diǎn)傳遞的、 G-邊傳遞的或G-弧傳遞的. 如果Aut(Γ)在Γ的頂點(diǎn)集、 邊集或弧集上是傳遞的, 則分別稱圖Γ是點(diǎn)傳遞、 邊傳遞或弧傳遞的.

圖的同構(gòu)問題的判斷, 是圖論研究以及決定圖的同構(gòu)類的基本問題. 對于Cayley圖, Cayley圖同構(gòu)問題研究起源于1967年Adam提出的一個猜想: 每個有限循環(huán)群都是DCI-群. 在過去的幾十年里, 該問題得到了廣泛的研究, 參見文獻(xiàn)[1-6]. 由于很多點(diǎn)傳遞圖并不是Cayley圖, 下一步的研究對象就由Cayley圖轉(zhuǎn)移到點(diǎn)傳遞圖上, 參見文獻(xiàn)[7]. 對于點(diǎn)傳遞圖, 希望能通過其點(diǎn)傳遞自同構(gòu)群來判斷它們是否同構(gòu), 即通過群G的性質(zhì)判斷兩個G-點(diǎn)傳遞圖是否同構(gòu).

一個G-點(diǎn)傳遞圖Γ=Cos(G, H, HSH)稱為G的GI-圖, 如果對于任意的圖Σ=Cos(G, H, HS′H), 當(dāng)Γ?Σ時, 存在τ∈Aut(G)使得Hτ=H, (HSH)τ=HS′H. 其中,GI表示群自同構(gòu)誘導(dǎo)的圖同構(gòu). 特別的, 當(dāng)H=1時, Γ是G的Cayley圖, 如果它是G的GI-圖, 則被稱作G的CI-圖.CI-圖在過去幾十年得到了廣泛的研究. 類似于Babai關(guān)于Cayley圖成為CI-圖的充分必要條件的研究, 本文討論了G-點(diǎn)傳遞圖成為G的GI-圖的充要條件, 研究了單群的點(diǎn)傳遞圖的GI-性質(zhì).

1　GI-圖的判別準(zhǔn)則

設(shè)G是一個群, H為G的子群, S為G的子集, 定義群G關(guān)于H和S的陪集圖Γ, 其中頂點(diǎn)集為V=[G:H], 對任意的Hx, Hy∈[G:H], Hx與Hy鄰接當(dāng)且僅當(dāng)yx-1∈HSH, 記作Γ=Cos(G, H, HSH). 當(dāng)H=1時, Γ=Cos(G, H, HSH)即為Cayley圖Cay(G; S). 在此, 給出陪集圖的一些性質(zhì).

性質(zhì)1

2) G傳遞地作用在點(diǎn)集[G:H]上, 作用的核恰好是H在G中的核, 即包含在H中的G的極大正規(guī)子群;

3) Γ是連通的當(dāng)且僅當(dāng)〈H, S〉=G;

4) Γ是G-弧傳遞的當(dāng)且僅當(dāng)存在元素g∈G, 有g(shù)2∈H, 且HSH=HgH.

引理2設(shè)Γ=(V, E)是群G的點(diǎn)傳遞圖， 則當(dāng)且僅當(dāng)Aut(Γ)中所有置換同構(gòu)于G的子群在Aut(Γ)中都是共軛的, Γ是G的GI-圖.

這一準(zhǔn)則類似于由Babai和Parsons得到的關(guān)于Cayley圖為CI-圖的判斷準(zhǔn)則. GI-圖的判斷準(zhǔn)則在Cayley圖同構(gòu)問題的研究中起著極其重要的作用, 參見文獻(xiàn)[8].

2　單群的點(diǎn)傳遞圖的GI-性質(zhì)

引理3設(shè)G是有限單群， 則G的外自同構(gòu)群都是可解的.

定理1設(shè)G是有限非阿貝爾單群, Γ是一個G-點(diǎn)傳遞圖. 若Aut(Γ)≤Aut(G), 則Γ是群G的GI-圖.

定理2令G是有限非阿貝爾單群, Γ是連通的三度G-對稱圖, 則：

1) (G,Aut(Γ))是(A7, A8)、 (A7, S8)、 (A7, Z2.A8)、 (A15, A16)、 (GL4(2), AGL4(2))之一;

2) Γ是G的GI-圖.

證明令X=Aut(Γ). 因為Γ是連通的G-弧傳遞圖, 所以X=GXv, 其中Xv是點(diǎn)v∈V(Γ)的穩(wěn)定子群. 若G不是X=Aut(Γ)的正規(guī)子群. 由文獻(xiàn)[11]中的定理7.1.3可知, (G,Aut(Γ))是(A7, A8)、 (A7, S8)、 (A7, Z2.A8)、 (A15, A16)、 (GL4(2), AGL4(2))之一. 下面假設(shè)G是X=Aut(Γ)的正規(guī)子群.

[1] ALSPACH B. Isomorphisms of Cayley graphs on abelian groups[M]// HAHN G, SABIDUSSI G. Graph symmetry: algebraic methods and applications. [S.l.]: Springer, 1997: 1-22.

[2] BABAI L. Isomorphism problem for a class of point-symmetric structures[J]. Acta Math Acad Sci Hungar, 1977, 29: 329-336.

[4] GODSIL C D. On the full automorphism group of a graph[J]. Combinatorica, 1981, 3(1): 243-256.

[5] GODSIL C D. On Cayley graph isomorphisms[J]. Ars Combin, 1983, 15: 231-246.

[6] SOMLAI G. Elementary abelianp-groups of rank 2p+3 are not CI-groups[J]. Journal of Algebraic Combinatorics, 2011, 34(3)： 323-335.

[7] DOBSON E. Isomorphism problem for metacirculant graphs of order a product of distinct primes[J]. Canadian Journal of Mathematics, 1998(6): 1 176-1 188.

[8] LI C H. On isomorphisms of finite Cayley graphs-a survey[J]. Discrete Mathematics, 2002, 256(1/2): 301-334.

[9] TUTTE W T. A family of cubic graph[J]. Mathematical Proceedings of the Cambridge Philosophical Society, 1947, 43(4): 459-474.

[10] TUTTE W T. On the symmetry if cubic graphs[J]. Canad J Msth, 1959, 11: 621-624.

[11] LI C H. Isomorphisms of finite Cayley graphs[D]. Perth: The University of Western Australia, 1997.

(責(zé)任編輯： 林曉)

The GI-properties of the vertex-transitive graphs of simple groups

CHEN Jing1, 2， QU Siyao2

(1. Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, Fuzhou, Fujian 350003, China;2. College of Mathematics and Computer Science, Hunan First Normal University, Changsha, Hunan 410205, China)

On the isomorphism problem of the vertex-transitive graphs, we give the criterion for a vertex-transitive graph to be a GI-graph, analogous to the conditions for a Cayley graph to be a CI-graph given by Babai. On basis of this, we attack the GI-properties of the vertex-transitive graphs of simple groups.

vertex-transitive graphs; simple groups; coset graphs; GI-graph

10.7631/issn.1000-2243.2016.01.0017

1000-2243(2016)01-0017-03

2015-08-31

陳靜(1983-)， 講師， 主要從事圖論的研究，chenjing827@126.com

國家自然科學(xué)基金資助項目 (11326057， 11501188)

O157.5

A