Uncoverings on graphs and network reliability

MaRDI QIDQ3101019zbMATH OpenFDO

Authors Robert F. Bailey, Brett Stevens

Publication date 22 November 2011

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

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)

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.

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

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)