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 ...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,19871040)Jiangsu 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.
