圈的2顶点扩张图的最大强直径的一个下界

A Lower Bound on the Maximum Strong Diameter Orientation of 2-Vertex Multiplications of Circles

给定一个无向图G,将G的每条边{x,y}用弧xy或yx替代后得到的有向图称为G的定向图.若连通图G在定向后是强连通的,则称该定向为G的强定向.使得G的所有定向图中强直径最大的定向称为G的最大强直径定向.文章给出了n-圈(其中n≥3)的2顶点扩张图的最大强直径的一个下界.

With a graph G given, we will obtain the oriented graph of G after replacing each side x,y of G with arc xy or yx. If the connected graph G is strongly connected after the orientation, the orientation is called the strong orientation of G. The orientation of all the oriented graphs of G which makes the strong diameter the largest is also called the maximum strong diameter orientation of G. A lower bound on the maximum strong diameter orientation of 2-vertex multiplication of n-circle（n is not less than 3）is given.