Mathematics – Combinatorics
Scientific paper
2010-12-14
Mathematics
Combinatorics
12 pages, 5 figures
Scientific paper
We propose a network protocol similar to the $k$-tree protocol of Itai and Rodeh [{\em Inform.\ and Comput.}\ {\bf 79} (1988), 43--59]. To do this, we define an {\em $t$-uncovering-by-bases} for a connected graph $G$ to be a collection $\mathcal{U}$ of spanning trees for $G$ such that any $t$-subset of edges of $G$ is disjoint from at least one tree in $\mathcal{U}$, where $t$ is some integer strictly less than the edge connectivity of $G$. We construct examples of these for some infinite families of graphs. Many of these infinite families utilise factorisations or decompositions of graphs. In every case the size of the uncovering-by-bases is no larger than the number of edges in the graph and we conjecture that this may be true in general.
Bailey Robert F.
Stevens Brett
No associations
LandOfFree
Uncoverings on graphs and network reliability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Uncoverings on graphs and network reliability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Uncoverings on graphs and network reliability will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-178618