Advances and Applications in Discrete Mathematics
Volume 3, Issue 2, Pages 85 - 108
(April 2009)
|
|
ON STRONG RABIN NUMBERS OF GRAPHS AND DIGRAPHS
Toru Kojima (Japan)
|
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).