雌不同构自补竞赛图的计数公式

《雌不同构自补竞赛图的计数公式》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、、＼}广西大学学报【自然科学短)VoI24N0．3lg9g年9月JournaLofGuangxiUmversity(NatSciEd)sept．1999厶第．雌2一朝不同构自补竞赛图的计数公式2九谭尚旺”张德龙(1)石油大学数学系，2)r：面j础科学部，柳州,545005；^辣一⋯嘶1性的错误结论．’关键词自补；同构；竞赛图分类号百7_丐_一——设S是集合X={1，2，⋯，n)上的n次对称群．∈S是一个置换，记^()表示置换中长为矗的圈的个数．特别地^Or)将表示中元素在的作用下不动点的数目．则Bu

2、rnside引理口’可表示为：命题A设H是S的子群，则置换群H的轨道数g(H)满足川T新^设丁：(，E)和=(，)是两个标定的阶竞赛图，={，口。，⋯，)如果对任意的巩，∈．当iTJEE时，都有．∈则称是T的补图．如果T和它的补图是同构的，记作丁：，则称了1是自补的．对于标定的n阶竞赛图T：(，E)，V一{-，口：，⋯，}，及任意的置换∈S令()：则此式定义了上的一个置换，从而S也可看成是用上述方法诱导出的上的置换群，因此S可以看成是标定的n阶竞赛图集合上的置换群．如果用for)表示在的作用下同构意

3、义上保持不变的阶标定自朴竞赛图的个数，则命题A可重新表示为：命题B记阶标定竞赛图中不同构的自补竞赛图的个数为W(n)，则有(n)=T∑，()．。⋯∈‘本文将利用命题B给出W(n)的具体表达式，来纠正文献[1]中关于自补竞赛图存在性的一个错误结论．设∈S，则／I"可以分解成互不相交圈的乘积，记中长为矗的圈的个数为d(矗一l，2，⋯，一)，则称()=(。⋯d⋯，d)为置换的型．显然1·十2·d4-⋯+n·d=．由自补竞赛图的定义易知成立下面事实：竞赛图：(，E)是自补的充分必要条件是，存在一个置换∈S，

4、使一切，∈V，当“∈E时，都有(“)(口)∈E．引理l设置换的型为()：(-，d2，⋯，d)．(1)如果d。≥2或存在≥l使”≠0，则fOr)一0．(2)如果每个≥0都有+=0，则，()：2，其中DOr)：专∑∑d,dr，)，这里(，)表示一^一1rL和的最大公约数．(3)如果d。=l并且对所有的≥l，都有d：：0，则for)=2A，其中面()=DOr)一寺．证设丁：(，E)是任意一个满足(丁．)：的阶竞赛图，于是丁是自补的，并且是同构意义收稿日期：1999—05—11第3期谭尚旺等：不同构自补竞赛

5、图的计数公式223下置换的一个不动点．把71分解成一系列子竞赛图71“，71，⋯，使它们满足下述条件：顶点和在同一个子竞赛图中，当且仅当和在的同一个圈中．于是在这一系列子竞赛图中阶为i的子竞赛图的个数为d，其中一1，2，⋯，一．(1)为方便，下面也用·简记．．首先，假设有长为2+1的躅．≥1．不妨设该圈为(1，2．3．⋯．2+1)并且1·2∈E．于是由是的不动点及所述事实知：1·2∈E(1)(2)一3·2∈E(2)(3)=3·4∈E⋯(2i+1)·(2i)∈E(2i)‘2i一1)=(2i+1)·l∈

6、E(1)(2i+1)一2·1∈E∈．从而和都在E中，这与竞赛图的定义矛盾．其中符号“”表示推出．其次，如果d≥2+则中存在两个不动点．不妨设为()和(，)，并且不妨夸．∈E于是口，，∈E()(．)一仉t】口J=口口∈E，这也是一个矛盾．综上知，当≥2或存在≥1使d21+t≠o时，不存在n阶竞赛图T满足(71)一亦即无不动点，从而for)=0．(2)设(P，Pz，⋯，P}和(¨+P+，⋯，户}分别是71的两个子竞赛图的顶点集，不妨设它们分别为71⋯和71，同时也不妨设所含有的两个2长和2f长圈分别为(

7、1，2，⋯，2k)和(2k+1，2k十2．⋯，2+21)．先确定71⋯中的弧．此时P和声，P；，⋯，P之间的k条弧可以任意定向，而71⋯的其余弧则在(71)=71条件下，根据所述事实由这k条弧的定向唯一确定．再确定71“和71’之间的弧，此时P和P+⋯P抖，⋯+PⅡ+Ⅲ之间的(2k，21)条弧可以任意定向，而71⋯与71之间的其余弧在条件(’)一71下+根据所述事实由这(2k，21)条弧的定向唯一确定．综上知，在构造满足(71)一的71时，可以任意定向的弧的总数为DOr)=∑d·导+∑()·(+∑·

8、(，f)一告∑∑·()．一1=L-<，^一lf—l因为每条弧的定向可有两种，因此在的作用下自补的阶竞赛图总数()：2．(3)不妨设唯一的一个一阶子竞赛图为7，其顶点集为(P)，而71是任意一个2r阶的子竞赛图，其顶点集为{P⋯P⋯，PH}，对应于中的两个躅设为(1)和(2，3+⋯，2r+1J．易知P与P，P。，⋯，P+。之间可以任意定向的弧只有一条+而其余弧定向据所述事实及条件(71)一71，将由这条弧的定向唯一确定+此表明71“和71之间可任意定向的弧的数目仍为1一