没有合适的资源?快使用搜索试试~ 我知道了~
幂图与Cayley图之间的关系研究
¼2¼¼加韦什加韦什Journal of the Egyptian Mathematical Society(2015)23,457埃及数学学会埃及数学学会www.etms-eg.orgwww.elsevier.com/locate/joems原创文章幂图与Cayley图的一些关系Sriparna Chattopadhyay*,Pratima Panigrahi数学系,印度技术学院Kharagpur,印度接收日期:2014年6月10日;修订日期:2014年11月12日;接受日期:2015年2015年4月16日在线发布本文受Abawajy等人[1]的一个公开问题的启发,发现了有限循环群的幂图与Cayley图之间的一些关系。证明了某些幂图的点消去子图是生成子图或等价于某些酉Cayley图的点消去子图的补图。我们还证明了某些Cayley图可以表示为作为幂图的直积。应用这些关系,我们研究了幂图和相关Cayley图的特征值和能量。2000年数学潜规则分类:05C25; 05C502015作者。制作和主办:Elsevier B.V.埃及数学学会的代表这是一篇CC BY-NC-ND许可证下的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。1. 介绍在过去的几十年里,半群或群的图表示的研究成为一个令人兴奋的研究课题,产生了许多有趣的结果和问题。在这方面,最流行的一类图是凯莱图。Cayley图在1878年被引入,得到了很好的研究,并有许多应用。功率图的概念是最近的发展。在本文中,我们研究了一个开放的*通讯作者。电子邮件地址:sriparnamath@gmail.com(S.Chattopadhyay),pratima@maths.iitkgp.ernet.in(P. Panigrahi)。同行评审由埃及数学学会负责制作和主办:Elsevierhttp://dx.doi.org/10.1016/j.joems.2015.01.004Abawajy等人的问题[1,问题10],要求功率图和凯莱图之间的有向幂图的概念首先由Kelarev和Quinn[2-4]引入并研究半群S的有向幂图是顶点集为S的有向图,且x;y存在从x到y的弧当且仅当x-y,yXm为一些积极整数M.在此之后Chakrabarty等人[5]定义了群G的无向幂图G_nG_n为顶点集为G且两个顶点u;v相邻的无向图当且仅当u在此之后,无向功率图成为了研究的主要焦点。[6-9]。文[5]证明了对任意有限群G,G的子群的幂图是G的导出子图,G是完备的当且仅当G是1阶循环群或pm,其中p是素数,m是正整数。Cameron在[6]中证明了,对于一个非素幂阶n的有限循环群G,1110- 256 X? 2015作者。制作和主办:Elsevier B.V.埃及数学学会的代表这是一篇基于CC BY-NC-ND许可证的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。关键词有限群;幂图;Cayley图;特征值;能量458S. Chattopadhyay,P. 帕尼格拉希ðÞ双-f环加雷什Þ¼ ð Þ加雷什Þ--Þ ¼ð - Þð Þ ð - Þð Þ ð Þ j 吉吉~2nnnnG的所有其他顶点都由G的单位元和生成元组成,使得jTnj<$1 <$$>/<$n <$$>,其中/<$n<$1是欧拉函数有关幂图的更多结果,请参阅最近的综述论文[1]。在本文中,我们的主要研究对象是无向功率图,所以我们使用简称对 于 有 限 群 G 和 G 的 不 含 单 位 元 e 且 满 足S-1<$fs-1 :s2Sg<$S的子集S,记法:设Tn是Zn 的 一 个 子 集 ,由单位元和生成元组成,即TnUn[f0g. 我们用Gω Zn和类似的CayωZn;Un<$Cay Zn ;Un<$-Tn表示图G Zn的顶点消去子图GZn-Tn.对于任意图G,设G是G的补图。定理2.1给出了G ω<$Zn<$与Cayω <$Zn;U n<$之间的关系,其中n为某些值.从幂图的定义可以清楚地看出,Tn的顶点相邻于具有连通集S;Cay G;S的Cayley图G是一个非连通图,顶点集为G且两个顶点g和h为相邻的当且仅当gh-12S.对于任何正整数n,所有其他的顶点在Gzn中。因此,粗略地说,这个定理给出了一个表达式,GZn表示为CayZn;U n,对于一类n值。由于CayZ;U是高度对称的,设Zn表示模n整数的加法循环群.如果我们用0; 1;... . ;n-1,则Un<$fa2Zn:gcd<$a;n<$$>1g是Zn的一个子集,阶为/<$n<$,其中/<$n <$是欧拉f函数Cayley图Cay<$Zn;Un<$被称为酉Cayley图,见[10].可以观察到,CayZn;Zn0是完全图K n 在n个顶点上。对于顶点集为fv1;v2;... ;vng,邻接矩阵AGaij被定义为n×n矩阵,其中如果vi~vj,则aij<$$>1,否则aij<$0。特征值也称为G的特征值,记为kiG;i ¼ 1; 2;.. . ; n. 因为AG是一个对称矩阵,这个定理也被广泛地研究在文献中,它可以帮助我们研究的结构和各种性质的Zn。例如,在下一节中,我们将应用这个定理来研究G_nZ_pq_n的本征值和能量,否则可能不那么容易得到。定理2.1. 如果n^pa qb,其中p;q是不同的素数,a;b是正整数,则Gω <$Zn <$是的一个生成子图,CayωZn; Un。 这些 两 图 是 平等 当且 仅当a 1/4b。证据 这两个图具有相同的顶点集Zn-Tn,kiG'sk1<$G<$P k2<$G<$P···P kn<$G<$. 由Perron FrobeniousTheo-其中T n<$U n[f0 g. LetEp<$fap2Zn:q-ag;Eq<$fbq2rem,见[11],k1G总是正的,并 且 对所有的i 2; 3;. . ;n.对于图G,G的能量E G,引入-由古特曼[12]引入的,是所有绝对值的总和其特征值。图的能量概念起源于化学。使用休克尔理论计算的某些共轭碳分子的总p-电子能量与其“分子"图的能量一致我们可以很容易地检验出完全图Kn的特征值是n-1和-1,其重数分别为1和n1所以E K n2 N1 .一、 一图G对n顶点是称为超能量如果E G>2 n 1 [13].在文献[14]中,作者找到了所有酉Cayley图的能量,并确定了能量满足的条件。他们精力充沛。由于Cayley图在自动机理论中的应用(如专著[15]中所解释的)和其他多方面的应用,[1]的作者给出了一个公开问题(问题10)来研究幂图和Cayley图的关系。本文给出了有限循环群Zn的幂图与Cayley图之间的一些关系。应用这些关系,我们得到了Zn及其相关Cayley图的特征值和能量,并找到了幂图和Cayley图的能量之间的关系.Zn:p-bg和E pq1/2 ftpq 2 Zng-f 0 g. 然后Ep;Eq,Epq是两两不相交的集合,其并集是Zn-Tn。首先研究图Cayω <$Zn; U n<$的顶点间的邻接性。如果可能的话,假设对于某些整数c和d;cp dp。则存在s Un使得对于某个整数r,cp(cp)s(dp)s(dp)s(dp)s(dp)d-c(dp)a-1qb(dp)p这 是 一 个 矛 盾 , 因 为 p-s. 所 以 对 于 任 何 整 数 c 和d;cp<$dp 。 类 似 地 , 可 以 证 明 对 于 任 何 整 数 c 和d;cq<$dq。因此,Ep;Eq中没有顶点与同一集合中的顶点相邻,并且Epq中的每个顶点都是孤立点,图Cayω <$Zn;U n<$.现在对于任何s2U n;gcdfs; nnn = 1,所以存在整数u和v,使得sun=1。考虑来自Ep的任何顶点ap和来自Eq的任何顶点bq。然后ap- bq ap-bqsu ap-bqsu mod n:因 为 p-apu-bqu 和 q-apu-bqu , 所 以 ap-bq 等 于 2Un , 所 以ap~bq.因此,Cayω <$Zn;Un<$是一个完全二部图,它的二部图Ep[Eq]与孤立顶点Epq. 所以在图Cayω <$Zn; U n<$中,Ep的顶点都不与Eq的任何顶点相邻,这是Cayω<$Z;U n <$中唯一的不相邻顶点.2. 幂图与Cayley图已知[10],如果n<$p是素数,则酉Cayley图Cay<$Zn;Un<$是完全图Kn接下来我们检查图G ω中顶点的非邻接性。如果可能的话,设图G ω <$Zn <$中Ep的ap与Eq的bq相邻.则对于一些正整数m1和m01,ap/mbq或 bq¼m0ap:如果n^pa是素数幂,则它是完全p-部11graph. 所以我们有下面的观察结果(i) 对任意素数p;GzZp;K p;Cayzp; U p;。(ii) 若n<$p a对某个素数p和一个大于1的正整数a,则Cay<$Zn;U n<$是G <$Zn<$的正则生成子图。首先考虑ap<$m1bq,这意味着ap<$m1bq<$m2pa qb一些m22z。但是Qjap是一个矛盾,q是一个素数,q-p也是q-a.因此ap-m1同样,可以证明bq-m01ap. 因此,Ep的顶点都不与Eq的任何顶点相邻。因此Gω<$Zn<$是Cayω <$Zn; U n<$的一个生成子图.幂图与Cayley图的关系459我p1ppp我特阿伊加雷什Þ加韦什.QQ我Q1p2KZpa i!Zn.则Cay<$Zn;S<$同构同构于首先考虑P1/4mpq。那么对于某个整数Cay Zn; S.事实上,群同构f:Zpa i!Zn是()f u 1;. ; u k-v 1;... ; v k2f群Zpai;16i6k,直积ZAI I 是集团()fu1;.. ; u k~ fv1;. ; v kin CayZn;S:12K12KZAI I1/1QQYkΣQ我.YY!我1/1p为 a/1/4b即 为 n<$pq;E pq<$$>/;E p <$fp; 2 p;. ;定理2.2. 设n<$p a1p a2···p ak 是的素分解Eq= 10pg和Eq^fq; 2 q;... g. 因此Cayω <$Zpq;Upq<$是一个完全二部图,具有二分图Ep[Eq,所以Cayω<$Zpq;Upq<$是Kq-1和Kp-1的不交并。再次a自然数n>1;S i¼Zpai - f0 g;i 1; 2;. ;k和SK被S的形象 下 的 上述 个提到的基团Ep[f0g]和Eq[f0g]在模pq加法下是闭的,分别是Zpq的q阶和p阶子群因此1/1QK1/1我Ep[f0g]和Eq[f0g]都是素数阶到GdZpa1GdZpa2·············GdZpak。和 所以 GINEp=Kq-1;GINEq=Kp-1。 因此 Gω <$Zpq<$是1 2k不相交 联盟 的Kq-1和 Kp-1和 所以 Gω Zpq证据 明确 格利兹aK a¼CayðZa;SÞ 为 所有 i¼1;CayωZpq ;U pq.第第piii2. ;k.现在从引理2.1开始,Cay= Za1;S1接下来我们取a>1。如果可能的话,假设Ep的p2是图G ω <$Zn<$中E pq的pq的相邻点。对一些人来说,CayZa2;S2CayZak;Sk¼Cay.QKKZpai;我是的。下正整数m和m0,p2½mpq或pq¼m0p2:2K. QK1/1Qk1/11/11/12Qkr;pmrp a-1q b-1q 这 是 一 矛盾因此1/1p2- m p q。 同样,可以证明pq-m0 p2. 因此当a>1时,两个图Gω<$Zn<$和Cayω <$Zn;Un<$不能也是图同构,即,它会保留相邻关系,如图所示下图:平等。 同样的道理也适用于b> 1。 因此GωZ n hu1;. ; u k~v1;.. . ; v kKawin Cay接下来,我们给出幂图和K1/1Zai;我KSi;1/1Cayley图使用图的直积概念作为也是群体的回想一下直积G1G2()u1;. ; u k-v1;.. . ; v k1/1 Si;图G11 1/4V1;E11 1/4和G21/4V2;E21/4是具有顶点集V1×V2,即V1和V2的乘积,以及. Yk !SI;因为f是双射在G1中,nu 1;u2n与nv1;v2n相邻G2当且仅当u1; v11/1在G1和u2中相邻v2在G2中相邻。此外,对于QK我1/1p()fu1;.. ; u k-fv1;.. . ; v k2 S; asf是群同态其中元素为1;... ;uk:ui2Zpaig和二进制运算u1;.. . ; u kv1;.. . ; v ku1v1;. 其中i分量中的加法是模p。因此f保持邻接,我们得到CayCayZpa 1;S1···CayZak;S kGZ a 1G···················· Zpak。HK1Ki1p p在定理2.2中,我们证明了,连通集S,Cayley图Cay<$Zn;S<$是Zn的幂图或Zn的适当真子群的幂图的直积.下面将使用Lemma 2.1证明这个定理。然而,这个引理与[16]的引理2.6相似,所以这里我们省略了它的证明。引理2.1. 对于不同的素数pi,正整数ai和子集S i<$Zpai; n i<$1;2;. ;k,Cay Zpa1;S1Cay我们通过一个例子来说明这个定理例1:让我们考虑群Z12<$Z4×Z3,其中Zn<$f 0 n; 1 n;. n-1n;g.因此,S1 1/4 f 1 4; 2 4; 3 4g; S21/4 f 1 3; 23g和S1/4f=S1×S21。 图GZ4、GZ3和Z4 Z3如图所示. 1和图二、f的图像因此S的元素可以应用中国剩余定理来计算。这里,S^f 112; 2 12; 5 12; 7 12; 10 12; 11 12g 因此,CayZ12;S 可以绘制为我K斯克拉普礁KZpai;1S岛图3.第三章。 从图图2和图3可以证明f是图同构 从图GZ4 GZ300 到图形联系我们CayZ12; S.记法:对于一个自然数n>1,我们取它的素数分解 作为 n/4p a1p a2···p ak, 哪里 p;p;.. . ; P是不同的素数和一个1;一个2;... k是正整数。是QK通过同构g:Zn!Q Zpai定义为:[a]a2;. . . ;1/2a]pak。我们考虑映射f/ g-11. 然后f:p2K1/1KZpai! Zn也是一个群同构。中的元素的图像K1/1ZAI 在f下可以计算我通过应用中国剩余定理图 1千兆赫兹3千兆赫兹和千兆赫兹4千兆赫兹。p同构f:我们证明,Zai;我SI已知 [17个] 的 Zn作为 组 (追加中)K我K460S. Chattopadhyay,P. 帕尼格拉希ðÞ þ我...p-2pqð Þ我...2Ka1aa2kðÞ加雷什 Þ ðÞ2pi2我12K1p2pK证据[11]证明了对任意n个顶点上的图G,k2G knG6 1.并且如果G是连通的,且G是一个完全二部图与若干孤立点的并[18][19][1 . ; n-1。现在,对于两个不同的素数p和q,GZpq是连通图,并且根据定理2.1,GZpq是Cayω<$Zpq;Upq<$$>和Tpq的顶点即G <$Zpq<$是图Kq-1;p-1加上/1个孤立点。因此kjGZpq<$<$1; j <$3; 4;. ; pq-1和kZp 1 q 1 6 1(因为K q - 1的最小特征值;p-1是-pp-1q-1)。这意味格鲁吉亚ÞÞ6pffiðffipffiffiffiffi-ffiffiffiffi1ffiffiffiÞffiðffiffiqffiffiffiffi-ffiffiffiffi1ffiffiÞffiffi-16pþq-2ðA:MPG:MÞ:图 2个千兆兹4个千兆兹3个千兆兹。2件装2ð2Þ由于kpq6kpq-1,从i得出右侧不等式。 再一次,众所周知(例如,看到[11])为任何图G对n顶点,k1G6n1和G的特征值之和为零。使用这些事实和等式。(1),(2)得到了左边不等式。从《古兰经》中可以看出,jkpqGZ-ZpqÞÞj6pþq:ð3Þ从Eqs。(1)- 1。然后ECayZn;SEGZpa1EGZa2···EGZakCay<$Zn;S<$将是定理2.2中给出的Zn的子集。在1/2磅 -1000磅 -1···p-1:5本节利用幂图与Cayley图的关系,研究了Zn和Cayley图的特征值和能量。 由于酉Cayley图的特征值和能量已得到了很好的研究(例如见[10,14]),我们比较了图G_n~ Z_n~ n的能量和CayZn;S与酉Cayley图的关系。在下面的定理中,我们应用定理2.1来找到GdZ pq的本征值和能量。定理3.1. 对于幂图GZpq,其中p和q是两个不同的素数,我们有以下内容。12k在下面的几个结果中,我们给出了幂图和Cayley图的能量的比较。推论3.1。对于n<$pq,其中p;q是不同的奇素数,E<$GqZn<$$>6E<$Cay<$Zn; S<$<$。证据 对于p1/3;q1/5,我们从(4)和(5)得到,EGZpq632¼ECayZpq;S:6现在,对于p;qP5,很容易验证,(i) k2GZpq6p<$q-2和kj<$Gzpq<$<$1;5pq-22pq这意味着,<E<$Cay<$Zn; S<$。证据众所周知,对任意n阶图G,k1<$G<$P2 M,其中M是G的边数。根据[5]的推论4.3,G ∈Z2q∈的边数M由下式给出:2M½4-/ 2-1]/2½2q-/q-1]/q½4q-/2q-1]/2q½24qq-1:因此情形二:这里k2;n pa qb pq.<我们考虑三个子情况:子情况1:p2; a1; n2 q b; 2
1;E CayZn; SPE CayZn; Un。证据 设n<$p a1p a2···p ak 是a的因为一个P2;一个P2- 4。首先我们考虑qb因为q是一个素数,q>2;> 0,所以从等式。(10)我们得到A>0。接下来我们考虑qb1/3。从EQ。(10)我们12K把A1/42a1- 6> 0作为P2。 A>0,对于所有自然数n>1。 因为对于所有i 1; 2;. ; k; p i是素数和ai是正整数则p a i - 1 P p a i - p a i-1。正整数a;b与P2和对所有素数q与q>2。从EQ。(9)得到E_(?)Cay_(?)Z_n;S_(?)所以把一个1-1磅的球传给一个2-1磅的球···把一个k-1磅的球传给他所以CayZn;S是高能的。12k子情况3:p;qP3;n<$p a q b;p2_n-1_n。然后通过1/n由[14]的定理3.7,可得E CayZn;Un2k/n.从Eqs。(5)和(8)我们得到ECayZn;SP2k/nECayZn;Un:Q由推论3.2和定理3.3,下面的推论是直接的。推论3.3。对于n1/2 q,其中q是奇素数,E<$GZn素数>E<$Cay<$Zn; U n素数。下一个定理给出了CayZn;S是超能的充要条件。将该定理与文献[14]中的定理3.10相比较,可以看出,CayZn;Un是超 能 的 , CayZn;S 也 是 超 能 的 . 然 而 , 对 于 某 些 n 值 ,Cay<$Zn;S<$是超能的,但Cay<$Zn;Un<$不是。定理3.4. 设n<$p a1p a2···p ak 是的素分解定理3.3,我们得到Cay<$Zn;S<$是超能的.情况III:这里kP3.这一情况类似于情况二的分案3。H确认作者感谢裁判员的宝贵建议。引用[1] J. Abawajy,A. Kelarev,M. Chowdhury,Power graphs:asurvey,Electron. J. Graph Theory Appl.1(2)(2013)125-147。[2] A.V. Kelarev,S.J. Quinn,群的组合性质和幂图,Contrib。 普通代数12(2000)229-235.[3] 张文龙,有向图与半群的组合性质,《代数学杂志》,2002年,第16[4] A.V. Kelarev,S.J. Quinn,半群的组合性质和幂图,评论。数学大学45(2004)1任何自然数n> 1。则Cay∈ Zn;S∈是超能的,如果且仅当n= 3或n= 2;n是奇数或n= 3;n是n的形式2 aqb对于某些正整数a;b有aP 2且q是奇素数。证据 我们考虑三种情况。情形I:对于k<$1;n<$pa,Cay<$Zn;S<$是完全图所以不是超能的。[5] I. Chakrabarty,S.戈什Sen,半群的无向幂图,半群论坛78(2009)410-426。[6] P.J. Cameron , The power graph of a finite group II , J.GroupTheory 13(2010)779[7] P.J. Cameron,S. Ghosh,有限群的幂图,离散数学311(2011)1220 - 1222。[8] S. Chattopadhyay,P. Panigrahi,有限循环二面角和双环群的幂图的连通性和平面性,代数离散数学。18(2014)42-49。一B462S. Chattopadhyay,P. 帕尼格拉希[9] M. Mirzargar,A.R. Ashra fi,M. J. Nadja fi-Arani,关于有限群的幂图,Filomat 26(2012)1201-1208。[10] W. Klotz , T.Sander , 酉 Cayley 图 的 一 些 性 质 ,Electron.J.Combin。14(2007)R45。[11] D.茨 韦 特 科 维 奇 山 口 Rowlinson , S.Simic',AnIntroductiontotheTheory of Graph Spectra , CambridgeUniversity Press,London,2010。[12] I. Gutman , The Energy of a Graph , Ber. 数 学 Stat. Sekt.Forschungszent.格拉茨103(1978)1-22。[13] X. Li,Y.施岛,智-地Gutman,Graph Energy,Springer,New York,2012.[14] H.N. Ramaswamy,C.R.Veena,关于酉Cayley图的能量,Electron.J.Combin。16(2009)N24。[15] 张文生,《图代数与自动机》,北京:计算机科学出版社,2003。[16] Y.G. Baik,Y.Q. Feng,H.S. Sim,M. Y.徐,关于阿贝尔群的凯莱图的正规性,代数学。 5(1998)297- 304。[17] T.W. Hungerford , 代 数 : 数 学 研 究 生 教 材 , Springer-Verlag,纽约,1974年。[18] X.杨,关于简单无向图的特征值分布,林。代数应用295(1999)73-80.
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- C++多态实现机制详解:虚函数与早期绑定
- Java多线程与异常处理详解
- 校园导游系统:无向图实现最短路径探索
- SQL2005彻底删除指南:避免重装失败
- GTD时间管理法:提升效率与组织生活的关键
- Python进制转换全攻略:从10进制到16进制
- 商丘物流业区位优势探究:发展战略与机遇
- C语言实训:简单计算器程序设计
- Oracle SQL命令大全:用户管理、权限操作与查询
- Struts2配置详解与示例
- C#编程规范与最佳实践
- C语言面试常见问题解析
- 超声波测距技术详解:电路与程序设计
- 反激开关电源设计:UC3844与TL431优化稳压
- Cisco路由器配置全攻略
- SQLServer 2005 CTE递归教程:创建员工层级结构
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功