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

Note on Bounded Length Paths of De Bruijn Digraphs

作　　者：徐俊明[1] 陶颖峰[1] 徐克力[1] 

机构地区：[1]中国科学技术大学数学系,合肥230026

出　　处：《中国科学技术大学学报》2002年第1期19-21,共3页JUSTC

基　　金：TheProjectSupportedbyNNSFofChina (No .199710 86)andNSFofAnhui (No .0 10 4 610 2 )

摘　　要：Imase等人证明了 :对于deBruijn有向图B(d ,k)中任何两个不同的顶点x和y ,存在d- 1条内点不交且长度都不超过k+ 1的 (x ,y)路 .但证明很长而且包含许多令人厌烦的验证 .Imase et al showed that for any two distinct vertices x and y of the de Bruijn digraph B(d,k), there are d-1 internally disjoint (x,y) paths of length at most k+1. A very short proof is given in this note.

关 键 词：限长路 Menger定理 DE BRUIJN有向图 顶点 内点 图论 

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