论文部分内容阅读
本文主要研究的是4度1-传递非1-正则Cayley图的分类以及半对称图的构造. 1947年Tutte证明了3度图至多是5-弧传递的.从此，小度数s-弧传递图的分类与刻画就引起了学者们的兴趣，并逐步发展成群与图研究的一个热门课题.本文在第三章给出了关于二面体群的4度(X，1)-传递非（X，1）-正则Cayley图Γ的一个粗略的分类.在图Γ的点稳定子群的阶不大于24时，得出点稳定子群在同构意义下有五种情况:D8，SmallGroup(16，3)，D16，SD16，D8×Z2;进而完全分类了图Γ满足群G在X中无核和4＜|Xv|≤24条件时的情况，得到此时Γ只能同构于八面体，完全二部图K4，4，w(5，2).或W(6，2).特别的，如果X=Aut(Γ)，则Γ在同构意义下只能是八面体. 半对称图是指正则的，边传递的，但非点传递的简单无向图.容易知道半对称图必然是半点传递的二部图，而且它的二部分的阶是相同的.我们在构造半对称图时，有一个困难:一个正则的边传递图通常是点传递的.1976年Folkman第一次系统地研究了半对称图，他构造出了一些半对称图的例子，并给出了最小的半对称图.在第四章中，我们得到了一种应用性较强的半对称图构造方法，而且给出了一类半对称图的无限族的例子:图Γ=Γ(q，p)，其中Γ是一个双陪集图，V(Γ)={(u,i)|u∈U，i∈Zq}∪{(w,i)|w∈W,i∈Zp},E(Γ)={{(u，i),(w，j)}|{u，w}∈E(Γ),i∈Zq,j∈Zp}.