On the Maximum Order of the Automorphism Group of a Planar Triply Connected Graph
On the Maximum Order of the Automorphism Group of a Planar Triply Connected Graph
复制标题
DOI：
10.1137/0114062
复制
发表时间：
1966-07
影响因子：
1.9
通讯作者：
L. Weinberg
中科院分区：
文献类型：
--
作者：
L. Weinberg
1.导论.每个线性图G，无论是有向的还是无向的，都有一组与之相关的自同构P F（G）;该组由G到自身的同构组成。我们考虑三连通平面图，并确定任何这样的图的P的最大阶。不失一般性，我们只考虑简单无向图。所谓简单图，我们指的是其中至多有一个分支连接任何一对节点的图;如果一个图有平行分支，即两个或多个分支关联到同一对节点，则该图是重图。本文所证明的定理也适用于有向图，因为有向图的群是它的无向图群的子群。类似地，它也适用于多重图，因为多重图的群是简单图的群的子群，简单图的群是通过删除每组平行分支中除一个分支之外的所有分支而得到的。在我们的讨论中，iPlatonic立体--四面体、立方体、八面体、十二面体和二十面体是重要的;更具体地说，我们考虑由它们的边和顶点形成的相应的平面图，并将这些称为Platonic图。本文的主要结果可用下面的定理来说明，该定理分两部分给出：定理1。(a)三连通平面图群的最大阶数为4 B，其中B为分支数. (b)此外，除了五个柏拉图图之外，每个三连通平面图的群F的阶都小于4 b，这些群中的每一个的阶都正好是4 b。
1. Introduction. Each linear graph G, whether directed or undirected, has a group of automorphisms P F (G) associated with it; this group consists of the isomorphisms of G to itself. We consider triply connected planar graphs and determine the maximum order of P of any such graph. Without loss of generality we consider only simple undirected graphs. By a simple graph we mean a graph in which atmost one branch joins any pair of nodes; if a graph has parallel branches, that is, two or more branches are incident to the same pair of nodes, the graph is a multigraph. The theorem proved in this paper applies to directed graphs because the group of a directed graph is a subgroup of the group ot its associated undirected graph. Similarly, it applies to multigraphs because the group of a multi-graph is a subgroup of the group of the simple graph obtained by deleting all butone branch of each set of parallel branches. The iPlatonic solids--the tetrahedron, the cube, the octahedron, the dodecahedron, and the icosahedronare important in our discussion; more specifically, we consider thecorresponding planar graphs formed by their edges and vertices and term these the Platonic graphs. The main result of this paper may be stated by the following theorem, which is given in two parts.THEOREM 1.(a) The maximum order of the group of a triply connected planar graph is 4b, where b is the number of branches.(b) In addition, the order of the groupF of every triply connected planar graph is less than 4b except for the five Platonic graphs, the order of each of these groups being precisely 4b.