n阶4、5度循环图的计数

Enumeration of Circulating Graphs with order n and Degree 4 and 5

将所有ｎ阶４度连通循环图所构成的集合记为Ｇ＿ｎ，Ｇ＿ｎ的元素个数记为｜Ｇ＿ｎ｜。文中首先导出了｜Ｇ＿ｎ｜的计算公式。然后将Ｇ＿ｎ中的图按图的同构关系分为一些等价类，进一步再将所有等价类按一定规则划分为Ⅰ型和Ⅱ型。记Ⅰ型等价类的个数为Ｔ，文中证明了ｎ阶４度不同构的连通循环图的个数有Ｔ个（当ｍ为偶时Ｔ为０），其中ｍ为小于ｎ且与ｎ互素的正整数个数的一半。同时文中也给出了ｎ阶５度不同构的连通循环图的类似的计算公式。

Let G. be a set of the circulating graphs with order n and degree 4 (or 5), |Gn| be thenumber of elements in Gn. The formula about |Gn|. is given in this peper. All equivalence classes which aredetermined by isomorphism relation of graphs are divided into two types:type Ⅰand type Ⅱ. Let T be thenumber of type Ⅰ, the present authors obtain the number of the non-isomorphic circulating graphs in T, where 2m is the number of peitive integers not exceeding n which arerelatively prime to n.