可引进群运算的两类平面图

Two Types of Planar Graphs in Which Group Operations Can Be Introduced

中文摘要:

      在某些文献中,我们常常看到图论与代数的概念及方法的密切联系和交错应用。例如,不久前,Babai等人即考虑了有敏锐的边可迁置换群的有向图,得到了关于这种图的最大外度数的估计的一些定理。而Bertram则反过来借助于图论的概念及方法,给出了关于有限群的某些数值(如非交换群中两两可换的一组元素的最大个数,等等)的大小的估计。 本文也将讨论群与图之间的联系。我们将使某些平面图的顶点与某些置换群的元素相对应,使顶点的序列与群元素的乘积相对应,然后通过对群的性质的研究,发现相应的平面图的顶点度数的一些规律,并据此解决

英文摘要:

      A planar graph G is called an I_n-gragh if the degree of every its interior vertex is an integer times n. In this paper we establish corresponding relations between degrees of vertices of the I₂ or I₃-graph and elements of the symmetric group Φ₃ of degree 3 or the alternating group Ψ₄ of degree 4. Moreover, we prove that for a hole-discrete I₂ or I₃-graph G, the product of the group's elements corresponding to the vertices of every hole is the unit elemente, iff V(G) is 3-colorable or orderedly 4-colorable.On these grounds, we find some regularities on degrees of vertices of these planar graphs, and solve a question on existence of planar graphs with some prescribed types of vertices and faces.