Uncoverings on graphs and network reliability

zbMATH Open1236.05159arXiv1012.2928MaRDI QIDQ3101019FDOQ3101019

Authors: Robert F. Bailey, Brett Stevens 

Publication date: 22 November 2011

Abstract: We propose a network protocol similar to the $k$-tree protocol of Itai and Rodeh [{em Inform. and Comput.} {�f 79} (1988), 43--59]. To do this, we define an {em $t$-uncovering-by-bases} for a connected graph $G$ to be a collection $mathcalU$ of spanning trees for $G$ such that any $t$-subset of edges of $G$ is disjoint from at least one tree in $mathcalU$, 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.

Full work available at URL: https://arxiv.org/abs/1012.2928

Recommendations

• Uniformly optimally reliable graphs: A survey
• scientific article; zbMATH DE number 6004906
• On reliability of graphs with node failures
• On the construction of optimally reliable graphs
• Uniformly optimally reliable graphs
• Network reliability in Hamiltonian graphs
• Bounding the Reliability of Networks
• Reliability of interconnection networks modeled by a product of graphs
• A reliability-improving graph transformation with applications to network reliability
• scientific article; zbMATH DE number 867686

zbMATH Keywords

graph decompositiongraph factorizationnetwork protocol\(t\)-uncovering-by-bases

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Cited In (3)

• Accessibility and reliability for connected bipartite graphs
• Graph theoretic characterization and reliability of the multiple-clique network
• Error-correcting codes from \(k\)-resolving sets

This page was built for publication: Uncoverings on graphs and network reliability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3101019)