圈的定向距离图的阶

The Orders of Orientation Distance Graphs of Cycles

图G的两个定向D与D′的定向距离d0(D,D′)是指与D′同构的定向与D之间不相同的弧数的最小值.G的定向距离图D0(G)的顶点是互不同构的定向,如果d0(D,D′)=1,则D与D′在D0(G)中相邻.确定了圈Cn(n 3)的定向距离图D0(Cn)的顶点数｜O(Cn)｜.

For two nonisomorphic orientations D and D′ of a graph G, the orientation distance d_0(D,D′) between D and D′ is the minimum number of arcs of D whose directions must be reversed to produce an orientation isomorphic to D′. The orientation distance graph D_0(G) of G has the set O(G) of pairwise nonisomorphic orientations of G as its vertex set and two vertices D and D′ of D_0(G) are adjacent if and only if d_0(D,D′)=1. This paper determines that the order |O(c_n)| of orientation distance graphs of cycles.