de Bruijn图的(1,2)-步竞争图

The (1,2)-step Competition Graph of the de Bruijn Digraph

设D=（VA）是一个有向图．有向图D的（1，2）一步竞争图是关于V（D）的无向图，表示为C1，2（D）．若边{x，y}∈E（C1，2（D）），当且仅当存在一个顶点z≠x，y，使得dD-y（x，z）≤1且dD-x（y，z）≤2或者dD-z（y，z）≤1且dD-y（x,z）≤2．在2000年，Cho等人给出了m-步竞争图的定义．主要研究了de Bruijn图的（1，2）-步竞争图，并给出了deBruijn图中的弧为C1，2（D）的边的一个刻画．

Given a digraph D = （V, A）. The （1, 2）-step competition graph of a digraph D, denoted by C1,2（D） is a graph on V（D）, where {x, y} ∈ E（C1,2（D）） if and only if there exists a vertex z ~ x, y such that either dD-y（x, z） ≤ 1 and dD-x（y, z） ≤2 or dD-x（y, z） ≤ 1 and dD-y（x, z） ≤ 2. The definition of m-step competition graph was given by Cho et al. in 2000. In this paper, we investigate the （1, 2）-step competition graph of the de Bruijn digraph and characterize the graph which is the edge of C1,2（D） from the arcs of the de Bruijn digraph DB （d, t）.