CAJ | 학술논문

循环图已被用于平行计算,网络等方面.循环图研究的一个基本问题是对互不同构的循环图进行计数.对于给定的一个正整数n,用C(n,k)表示互不同构的具有几个顶点,度数为k的连通循环图的个数.文中给出了度数为4和5的循环图的一般结构,并对n=paqb(p,q皆为素数,a,b＞0).给出了C(n.4)的计算公式.
순배도이피용우평행계산,망락등방면.순배도연구적일개기본문제시대호불동구적순배도진행계수.대우급정적일개정정수n,용C(n,k)표시호불동구적구유궤개정점,도수위k적련통순배도적개수.문중급출료도수위4화5적순배도적일반결구,병대n=paqb(p,q개위소수,a,b＞0).급출료C(n.4)적계산공식.
Circulant graphs have been applied to Ramsey type problem,parallel computing and networks.A basic problem in research of circulant graphs is counting nonisomorphic circulant graphs.Given positive integers n and k,let C(n,k) denote the number of connected and pairwise nonisomorphic circulant graphs having n vertices and valency k.In this paper first we obtain C(n,5) by using the parameters C(n,4) and C(n/2,4).Then we investigate structure of circulant graphs with valency 4 for computing C(n,4).Finally,as an application of the previous results,we calculate C(n,4),for n = pa qb with p,q primes and a,b ≥ 0.