有向Cayley图的直径

DIAMETERS OF CAYLEY DIGRAPHS

设Ｇ是一个有限Ａｂｅｌ群，Ｍ是Ｇ的一个二元生成集．Ｇ上的有向Ｃａｙｌｅｙ图Ｄ（Ｃ，Ｍ）是一个以Ｇ为顶点集的有向图，若ｘ，ｙ∈Ｇ，则存在ｘ到ｙ的弧当且仅当ｙ－ｘ∈Ｍ．Ｎ个顶点的所有这种有向Ｃａｙｌｅｙ图的最小直径和平均距离是多少？我们将此问题转化为一个几何问题并由此得到了直径的一个下－２和平均距离的一个下界．这两个界仅当Ｎ＝３ｘ２时可达，这里ｘ是任一自然数．

The problems under consideration arise from local networks,such networks are often modeled as digraphs of some symmetry properties.espeially Cayley digraphs. Let G ie a finite alelian group with two elements genersting set M. Consider the Cayley digraph D(C.M) of a group C in which the venices are corresponding the elements of G and there is an arc from x to yiffy-x ∈ M. What is the minimum values of the diameters and/or the average distances all such Caylty digraphs on N vertices? We transformed this problem into a geometrical version and obtain a lower bound for the average distances. Furthermor,these for the diameters and a lower bound. for the average distance Furthermor,thesetwo bounds are attained if f N = 3x2 for some positive integer x. We also characterize a class of Cayley digraphs of finite abelian groups with degree 2 the diameter and average distance of evety digraph in this class are known and every Cayley digraph of a finite atelian group with degree 2 is isomorphic to one of this class.