有向循环图与有向圈的乘积的研究

Research on the Product of Cirulant Digraph and Directed Cycle

本文讨论了有向循环图与有向圈的乘积 ,得到了以下结果 :( 1)有向循环图D(n ;s1,s2 ,… ,si- 1,nl ,si+1,… ,sr)是连通的充要条件。( 2 )设有向循环图D(n ;s1,s2 ,… ,si- 1,s,si+1,… ,sr)连通 ,且n =ls,gcd(n ,s1,s2 ,si- 1,si+1,… ,sr) =l(l>2 ) ,则D(n ;s1,s2 ,si- 1,s,si+1,… ,sr) D(s ;s1l,s2l ,… ,si- 1l ,si+1l ,… ,srl)× μl。( 3)设D(n0 ;s1,s2 ,… ,sr)是连通 ,则D(n0 ;s1,s2 ,… ,sr)×μn1× μn2 ×… μns为有向循环图 gcd(ni,nt) =1(i,t =0 ,1,2 ,… ,s ;i≠t)。gcd(n ,s1,s2 ,… ,sr)表示n ,s1,s2 ,… ,sr 的最大公约数 ,μl

In this paper the product of the circulant digraphs and directed cycle is discussed.We use gcd(n,s 1,s 2,s r) to denote the greatest common divisor of n,s 1,s 2,…,s r,and μ l the dicycle with l vertices.The following results are obtained. 1)Necessary and sufficient condition of circulant digraph D(n;s 1,s 2,…,s i-l ,nl,s i+1 ,…,s r)is connected. 2)Suppose that gcd(n,s 1,s 2,…,s i-1 ,s i+1 ,…,s r)=l(l>2),n=ls,and D(n;s 1,s 2,…,s i-1 ,s,s i+1 ,…,s r)is connected.Then D(n;s 1,s 2,…,s i-1 ,s,s i+1 ,…,s r)D(s;s 1l,s 2l,…,s i-1 l,s i+1 l,…,s rl)×μ l。 3)Suppose that D(n 0,s 1,s 2,…,s r) is connected.Then D(n 0,s 1,s 2,…,s r)×μ n 1 ×μ n 2 ×…×μ n s (s i≠nl;1≤i≤r) is a circulant digraphgcd(n i,n t)=1(i,t=0,1,2,…,s;i≠t)。