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

Directed Cycle Length Distribution of Digraphs

阶为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.