|
|
| |
| A NEW PROPERTY OF BINARY UNDIRECTED de BRUIJN GRAPHS |
| |
Citation： |
XU Junming.A NEW PROPERTY OF BINARY UNDIRECTED de BRUIJN GRAPHS[J].Chinese Annals of Mathematics B,2000,21(1):39~42 |
| Page view： 1107
Net amount： 684 |
Authors： |
XU Junming; |
Foundation： |
Project supported by the National Natural Science Foundation of China (No. 19971086 and 1987-1040) and the Jiangsu Provincial Natural Science Foundation of China. |
|
|
| Abstract： |
The authors obtain a new property of the $n$-dimensional binary undirected de Bruijn graph $UB(n)$ for $n\ge 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\ge 4$. |
Keywords： |
de Bruijn graph, Wide-diameter, Length of path, Dominating number |
Classification： |
05C40, 68M10, 68R10 |
|
|
Download PDF Full-Text
|
|
|
|
