On the diameter of the generalized undirected de Bruijn graphs UG B(n, m), n2 < m ≤ n3

Jyhmin Kuo*, Hung-Lin Fu

*Corresponding author for this work

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

The generalized de Bruijn digraph GB(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 GB(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 2n2 ≤m≤n3 the diameter of UGB(n, m) is equal to 3. We also show that for pairs (n, m) where n2 < m < 2n2 the diameter of UGB(n, m) can be 2 or 3.

Original languageEnglish
Pages (from-to)180-182
Number of pages3
JournalNetworks
Volume52
Issue number4
DOIs
StatePublished - 1 Dec 2008

Keywords

  • Diameter
  • Generalized de Bruijn graph
  • Undirected graph

Cite this