# Technical Report CS0895

 TR#: CS0895 Class: CS Title: On the Total$_k$-Diameter of Connection Networks Authors: Ye. Dinitz, T. Eilam, Sh. Moran, and Sh. Zaks PDF CS0895.pdf Abstract: We define the related notions of {\em total$_k$-distance} for a pair of nodes and {\em total$_k$-diameter} of a connection network, and study the value $\TD_k(d)$ which is the maximal such total$_k$-diameter of a network with diameter $d$. These notions have applications in fault-tolerant routing problems, in ATM networks, and in compact routing in networks. We prove an upper bound on $\TD_k(d)$ and a lower bound on the growth of $\TD_k(d)$ as functions of $k$ and $d$; those bounds are tight, $\theta(d^k)$, when $k$ is fixed. Specifically, we prove that $\TD_k(d) \leq 2^{k-1}d^k$, with the exceptions $\TD_2(1) = 3$, $\TD_3(1) = 5$, and that for every $k,d_0>0$, there exists (a) an integer $d \geq d_0$ such that $\TD_k(d) \geq d^k/k^k$, and (b) a $k$-connected simple graph $G$ with diameter $d$ such that $d \geq d_0$, and $td_k(G) \geq (d-2)^k/k^k$. . Y Copyright The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1997/CS/CS0895), rather than to the URL of the PDF files directly. The latter URLs may change without notice.