### Abstract

The generalized de Bruijn digraph G_{B}(n, m) is the digraph (V, A) where V = {0,1.....m-1}and (i,j) ∈ A if and only if j ≡ in + α (mod m) for some α ∈ {0,1,2.....n-1). By replacing each arc of G_{B}(n, m) with an undirected edge and eliminating loops and multi-edges, we obtain the generalized undirected de Bruijn graph UG _{B}(n, m). In this article, we prove that when 2n^{2} ≤m≤n^{3} the diameter of UG_{B}(n, m) is equal to 3. We also show that for pairs (n, m) where n^{2} < m < 2n^{2} the diameter of UG^{B}(n, m) can be 2 or 3.

Original language | English |
---|---|

Pages (from-to) | 180-182 |

Number of pages | 3 |

Journal | Networks |

Volume | 52 |

Issue number | 4 |

DOIs | |

State | Published - 1 Dec 2008 |

### Keywords

- Diameter
- Generalized de Bruijn graph
- Undirected graph

## Cite this

Kuo, J., & Fu, H-L. (2008). On the diameter of the generalized undirected de Bruijn graphs UG

_{B}(n, m), n^{2}< m ≤ n^{3}.*Networks*,*52*(4), 180-182. https://doi.org/10.1002/net.20228