关于定向图及其逆图的控制(英文)

On Domination of Orientations and Their Reverses in Graphs

将图G的每条边任意赋予一个方向得到它的一个定向图G.G的逆图即为改变它的每条弧的方向所得到的图.用G-表示.C(G)为定向图G的控制数.首先刻画了满足C(G)=C(G-)的定向图G,并给出其控制数的紧的界,其次讨论了拥有此类定向图的无向图的相关性质.关于路或者圈,他们的定向图及其逆图的控制数的差可以无限大.

Let G be an orientation of G obtained by replacing each edge by a directed arc with the same ends. G- is denoted as its reverse obtained by reversing all the arcs of G. ）γ（G） is the domination number of G. The sharp bounds for orientation G that satisfies γ（G）=γ（G-） are given and classes of undirected graphs that admit such orientations are discussed. As with paths or cycles, it＇s claimed that the differences of domination numbers between their orientations and corresponding reverses can be arbitrarily large.