有向图的有向圈长分布(英文)  

Directed Cycle Length Distribution of Digraphs

作　　者：李炜 施永兵[2] 

机构地区：[1]英新达(上海)电子有限公司 [2]上海师范大学数理信息学院,上海200234

出　　处：《上海师范大学学报（自然科学版）》2003年第2期23-27,共5页Journal of Shanghai Normal University(Natural Sciences)

基　　金：Supported by the Foundation of the Development of Science and Technology of Shanghai Higher learing(02KD08)

摘　　要：阶为v的有向图D的有向圈长分布是序列(c_1,c_2,…,c_v),其中C_i是D中长为i的有向圈的数目。设0≤x_i≤v-i-1,证明了存在v个顶点的有向图D,使D的有向圈长分布为(0,0,x_1,x_2,…,x_(v-3),1),并且给出了具有有向圈长分布为(0,0,x_1,x_2,…,x_(v-3),1)的有向图的最大可能的弧数以及具有有向圈长分布为(0,0,k,k,…,k,k-1,…,3,2,1)(其中1≤k≤v-2)的有向图的最小可能弧数的上界。The directed cycle length distribution( DCLD) of a digraph of order v is the sequence (c,,c2,晻?c,),weher Ci is the number of directed cycles of length i.Let 0<xi<v-i-1 for i=1,2,...,v-3.In this paper,we prove that there exists a digraph of order v such that its DCLD is ( 0,0,x1,,x2,...,xx-3,1),determine the maximum possible number of arcs in a digraph whose DCLD is (0,0,x1,x2,...,xx-3,1) and obtain a upper bound of the mini-num possible numbe of arcs in a digraph whose DCLD is (0,0,k,k,...,k,k-1,...,3,2,1) for 1<k<v-2.

关 键 词：有向图 有向圈 圈长分布 

分 类 号：O157.5[理学—数学]