A NEW PROPERTY OF BINARY UNDIRECTED de BRUIJN GRAPHS

The authors obtain a new property of then-dimensional binary undirected de Bruijn graphUB(n) forn ≥ 4, namely, there is a vertexx such that for any other vertexy there exist at least two internally disjoint paths of length at mostn- 1 betweenx andy inUB(n). The result means that the (n-1, 2)-dominating number ofUB(n) is equal to one ifn ≥ 4. Project supported by the National Natural Science Foundation of China (No. 19971086 and 1987-1040) and the Jiangsu Provincial Natural Science Foundation of China.