Uncoverings on graphs and network reliability

Details Uncoverings on graphs and network reliability Uncoverings on graphs and network reliability

2010-12-14

arxiv.org/abs/1012.2928v2

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.

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-178618