论文部分内容阅读
决定Cayley图的自同构群是代数图论中一个非常重要也十分活跃的研究课题.一般来说,要解决这个问题是非常困难的.近几十年来,虽然关于Cayley图的自同构群已有很多结果,但是到目前为止,这个问题仍没有希望能够得到完全解决.本文主要决定了几类重要Cayley图,如:错位图、偶错位图的张量幂以及著名的烙饼图的自同构群,也刻画了其中一些图类的重要不变量,如:色数、团数、独立数及谱等.值得一提的是,本文反复运用图的最大独立集的结构来决定它的自同构群,这种方法在目前已有的自同构群研究中还不多见.本文工作主要围绕以下几个方面.首先,关于错位图,我们证明它的自同构群是(R(Sn)(?) Inn(Sn))(?) Z2,其中只(Sn)和Inn(Sn)分别是对称群Sn的右正则表示和内自同构群,Z2是Sn上的取逆映射生成的二阶循环群;通过证明上述结果,我们得到一个对称群上满足某一条件的任意Cayley图的自同构群的阶的上界.利用错位图的自同构群的结果,我们完全刻画了错位图的所有边轨道.另外,我们研究了它的谱,通过推导出一个它的对应于二部划分的特征值公式,我们决定了它的第二大特征值;作为这个结果的应用,我们给出了错位图等周常数的上下界,同时,也得到它的二部密度的上界及香农容量的确切值.其次,对于偶错位图的张量幂,我们刻画了它的一些性质,包括:连通性、直径、独立数、团数、色数等,并证明它的所有最大独立集都是点稳定子的陪集,这推广了Ku和Wong [59]的一个结果;通过应用它的最大独立集的特殊结构,我们证明:偶错位图的q次张量幂的自同构群是(R(Anq)(?)(Inn(Sn)(?)(Sn))(?)Z2q,其中只(Anq)是交错群直积Anq的右正则表示,Inn(Sn)是对称群Sn的内自同构群, Zq2表示二阶循环群的直积, Inn(Sn) Sq代表Inn(Sn)和Sq的圈积.最后对于烙饼图,通过运用它的有效控制集的刻画结果,并深入分析图本身的结构,我们证明:烙饼图的自同构群同构于对称群的右正则表示,即烙饼图是对称群的一个图正则表示.此外,我们也研究了烙饼图的上连通性和超连通性.