Header menu link for other important links
X
Oriented diameter of star graphs
K.S.A. Kumar, , K.S. Sudeep
Published in Elsevier B.V.
2021
Volume: 319
   
Pages: 362 - 371
Abstract
An orientation of an undirected graph G is an assignment of exactly one direction to each edge of G. Converting two-way traffic networks to one-way traffic networks and bidirectional communication networks to unidirectional communication networks are practical instances of graph orientations. In these contexts minimising the diameter of the resulting oriented graph is of prime interest. The n-star network topology was proposed as an alternative to the hypercube network topology for multiprocessor systems by Akers and Krishnamurthy (1989). The n-star graph Sn consists of n! vertices, each labelled with a distinct permutation of [n]. Two vertices are adjacent if their labels differ exactly in the first and one other position. Sn is an (n−1)-regular, vertex-transitive graph with diameter ⌊3(n−1)∕2⌋. Orientations of Sn, called unidirectional star graphs and distributed routing protocols over them were studied by Day and Tripathi (1993) and Fujita (2013). Fujita showed that the (directed) diameter of this unidirectional star graph Sn⃗ is at most ⌈5n∕2⌉+2. In this paper, we propose a new distributed routing algorithm for the same Sn⃗ analysed by Fujita, which routes a packet from any node s to any node t at an undirected distance d from s using at most min{4d+4,2n+4} hops. This shows that the (directed) diameter of Sn⃗ is at most 2n+4. We also show that the diameter of Sn⃗ is at least 2n when n≥7, thereby showing that our upper bound is tight up to an additive factor. © 2021 Elsevier B.V.
About the journal
JournalData powered by SciSpaceDiscrete Applied Mathematics
PublisherData powered by SciSpaceElsevier B.V.
ISSN0166218X
Open AccessNo