ON STRONG RABIN NUMBERS OF GRAPHS AND DIGRAPHS

Toru Kojima (Japan)

Received February 9, 2009

Abstract

Let k be a positive integer and let G be a k-connected graph or digraph. The k-Rabin number  of G is the minimum l such that for every  distinct vertices  there exist k vertex-disjoint (except at x) paths of length at most l from x to  There       is a generalization of the k-Rabin number, called the strong k-Rabin number  in which  are not necessarily distinct. We remark that  In this paper, we give an upper bound of strong k-Rabin numbers of k-connected (di)graphs which   satisfy a condition. As applications, we get an upper bound of the strong Rabin number of de Bruijn digraph  Furthermore, this result can be used not only to resolve some known strong Rabin numbers of (di)graphs but also to determine unknown strong Rabin numbers of Kautz digraph  and star network  (n is odd).

Keywords and phrases: Rabin number, strong Rabin number, wide diameter, fault diameter.