The authors obtain a new property of the n-dimensional binary undirected de Bruijn graph UB(n) for n ≥4, namely, there is a vertex x such that for any other vertex y there exist at least two internally disjoint paths...The authors obtain a new property of the n-dimensional binary undirected de Bruijn graph UB(n) for n ≥4, namely, there is a vertex x such that for any other vertex y there exist at least two internally disjoint paths of length at most n - 1 between x and y in UB(n). The result means that the (n - 1, 2)-dominating number of UB(n) is equal to one if n ≥4.展开更多
基金National Natural Science Foundation of China !No. 19971086,19871040Jiangsu Provincial Natural Science Foundation of China
文摘The authors obtain a new property of the n-dimensional binary undirected de Bruijn graph UB(n) for n ≥4, namely, there is a vertex x such that for any other vertex y there exist at least two internally disjoint paths of length at most n - 1 between x and y in UB(n). The result means that the (n - 1, 2)-dominating number of UB(n) is equal to one if n ≥4.