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.