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

作者：张雪飞; 宋爱斌; 郑素文; 罗俊芝; 宫雷

来源：数学的实践与认识, 2018, 48(20): 138-142.

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

设D=(V,A)是一个有向图.有向图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-x(y,z)≤1且dD-y(x,z)≤2.在2000年,Cho等人给出了m-步竞争图的定义.主要研究了deBruijn图的(1,2)-步竞争图,并给出了deBruijn图中的弧为C1,2(D)的边的一个刻画.

• 单位
  中国人民解放军装甲兵工程学院