Department of Applied Mathematics & Physics, Kyoto University

### Technical Report 2011-011 (April 05, 2011) Improved Bounds for Minimum Fault-Tolerant Gossip Graphs by Toru Hasunuma, Hiroshi Nagamochi

A $k$-fault-tolerant gossip graph is a (multiple) graph whose edges are linearly ordered such that for any ordered pair of vertices $u$ and $v$, there are $k+1$ edge-disjoint ascending paths from $u$ to $v$. Let $\tau(n,k)$ denote the minimum number of edges in a $k$-fault-tolerant gossip graph with $n$ vertices. In this paper, we present upper and lower bounds on $\tau(n,k)$ which improve the previously known bounds. In particular, from our upper bounds, it follows that $\tau(n,k) \leq \frac{nk}{2} + O(n\log{n})$. Previously, it has been shown that this upper bound holds only for the case that $n$ is a power of two.