关于de Bruijn图中限长路的注记(英文)

Imase等人证明了 :对于deBruijn有向图B(d ,k)中任何两个不同的顶点x和y ,存在d- 1条内点不交且长度都不超过k+ 1的 (x ,y)路 .但证明很长而且包含许多令人厌烦的验证 .

点线系统及其推广

在Sylvester-Gallai定理与Erdos-de Bruijn定理的基础上,对点线系统的分类与计数问题进行研究,给出了点线系统中线的数量的计算公式与取值范围,并给出点线系统的若干推广,同时对广义点线系统与区组设计之间的关系进行了讨论,对区组设计的一些基本定理进行了推广.

几个著名网络的限长路径(英文)

设给出了(h,(?))-η限长路径问题是图论中的Menger定理的变形和推广,在实时容错网络设计和分析中有重要意义.对于给定的正整数d,Ad(D)表示网络D中任何距离至少为2的两顶点之间内点不交且长度都不超过d的路的最大条数;Bd(D)表示D的顶点子集B中的最小顶点数使得D-B的直径大于d.已证明确定Ad(D)的问题是NPC问题,而且显然有不等式Ad(D)《 Bd(D).本文考虑D为超立方体网络、De Bruijn网络和Kautz网络,对d的不同值确定了Ad(D)及Bd(D),而且均有Ad(D)=Bd(D).