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

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

作　　者：张雪飞 宋爱斌 郑素文 罗俊芝 宫雷 ZHANG Xue-fei;SONG Ai-bin;ZHENG Su-wen;LUO Jun-zhi;GONG Lei(Basic Education Department,Army Academy of Armored Forces,Beijing 100072,China)

机构地区：[1]陆军装甲兵学院基础部

出　　处：《数学的实践与认识》2018年第20期138-142,共5页Mathematics in Practice and Theory

基　　金：学院科研创新基金项目(2016CJ01,2016CJJCBXJ03)

摘　　要：设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）.

关 键 词：DE BRUIJN图 (1 2)-步竞争图 路 

分 类 号：O157.5[理学—数学]