A more detailed classification of symmetric cubic graphs
A more detailed classification of symmetric cubic graphs
复制标题
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
M. Conder;R. Nedela
中科院分区：
文献类型：
--
作者：
M. Conder;R. Nedela
图Γ是对称的，如果它的自同构群传递作用于Γ的s-弧，如果它的自同构群正则作用于Γ的s-弧集合。Tutte（1947, 1959）证明了对于某些s≤5，每一个三次有限对称三次图都是s正则的。djokovije和Miller（1980）证明了有限三次图上有七种类型的弧传递群作用，其特征是顶点和边的稳定子。然而，给定的有限对称三次图可能存在一种以上的弧传递群作用。在本文中，我们准确地确定了哪些类型的组合是可能的。有些组合很容易被现有的理论所消除，而另一些则可以通过该理论的基本扩展来消除。其余的组合给出了17类有限对称三次图，并对每一类图证明了该类是无限的，并确定了至少一个代表。对于这17个类中的至少14个，我们给出的代表性具有最小可能数量的顶点（并且我们表明，在这14个案例中的两个案例中，该类中的每个图都是最小代表性的覆盖），而对于其他三个类，我们给出了已知的最小示例。在附录中，我们给出了一个表，显示了每一个最多768个顶点的对称三次图的类。
A graph Γ is symmetric if its automorphism group acts transitively on the arcs of Γ, and s-regular if its automorphism group acts regularly on the set of s-arcs of Γ. Tutte (1947, 1959) showed that every cubic finite symmetric cubic graph is s-regular for some s ≤ 5. Djokovič and Miller (1980) proved that there are seven types of arc-transitive group action on finite cubic graphs, characterised by the stabilisers of a vertex and an edge. A given finite symmetric cubic graph, however, may admit more than one type of arc-transitive group action. In this paper we determine exactly which combinations of types are possible. Some combinations are easily eliminated by existing theory, and others can be eliminated by elementary extensions of that theory. The remaining combinations give 17 classes of finite symmetric cubic graph, and for each of these, we prove the class is infinite, and determine at least one representative. For at least 14 of these 17 classes the representative we give has the minimum possible number of vertices (and we show that in two of these 14 cases every graph in the class is a cover of the smallest representative), while for the other three classes, we give the smallest examples known to us. In an Appendix, we give a table showing the class of every symmetric cubic graph on up to 768 vertices.