Premium
2‐diameter of de Bruijn graphs
Author(s) -
Li Qiao,
Sotteau Dominique,
Xu Junming
Publication year - 1996
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199608)28:1<7::aid-net2>3.0.co;2-j
Subject(s) - de bruijn sequence , combinatorics , de bruijn graph , disjoint sets , vertex (graph theory) , mathematics , undirected graph , graph , binary number , discrete mathematics , arithmetic
This paper shows that in the undirected binary de Bruijn graph of dimension n, UB(n), which has diameter n, there exist at least two internally vertex disjoint paths of length at most n between any two vertices. In other words, the 2‐diameter of UB(n) is equal to its diameter n. © 1996 John Wiley & Sons, Inc.