How robust is the n-cube?

DOI10.1016/0890-5401(88)90056-9zbMath0647.68007OpenAlexW2005280076MaRDI QIDQ1104728

Bernd Becker, Hans Ulrich Simon

Publication date: 1988

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(88)90056-9

zbMATH Keywords

chromatic numberfaulty processorfaulty linkn-cube networkdirected chromatic index

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Theory of software (68N99)

Related Items

On the extremal combinatorics of the Hamming space ⋮ Measuring teachability using variants of the teaching dimension ⋮ Distributed computing on oriented anonymous hypercubes with faulty components ⋮ Robustness of star graph network under link failure ⋮ Hypercube sandwich approach to conferencing. ⋮ Application of coding theory to interconnection networks ⋮ Fault tolerance in \(k\)-ary \(n\)-cube networks ⋮ Improving bounds on link failure tolerance of the star graph ⋮ Partial covering arrays: algorithms and asymptotics ⋮ SOME RESULTS ON BUDS, STEMS AND FAULT TOLERANCE IN HYPERCUBES OF DIMENSION ⋚ 5 ⋮ Fault tolerance in bubble-sort graph networks ⋮ The preclusion numbers and edge preclusion numbers in a class of Cayley graphs ⋮ Subnetwork preclusion for bubble-sort networks ⋮ On \(n\)-column 0,1-matrices with all \(k\)-projections surjective

Cites Work

• Solutions to Edmonds' and Katona's problems on families of separating subsets
• Every planar map is four colorable. II: Reducibility
• A generalization of results of P. Erdős, G. Katona, and D. J. Kleitman concerning Sperner's theorem
• Families of \(k\)-independent sets
• A decomposition theorem for partially ordered sets
• The Indirect Binary n-Cube Microprocessor Array
• Diameter bounds for altered graphs