Premium
On the diameter of the generalized undirected de Bruijn graphs UG B ( n , m ), n 2 < m ≤ n 3
Author(s) -
Kuo Jyhmin,
Fu HungLin
Publication year - 2008
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/net.20228
Subject(s) - combinatorics , digraph , de bruijn sequence , undirected graph , mathematics , de bruijn graph , graph
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 ≡ i n + α (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 U G B ( n , m ). In this article, we prove that when 2 n 2 ≤ m ≤ n 3 the diameter of U G B ( n , m ) is equal to 3. We also show that for pairs ( n , m ) where n 2 < m < 2 n 2 the diameter of U G B ( n , m ) can be 2 or 3. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008