Largest component and node fault tolerance for grids

DOI10.37236/8376MaRDI QIDQ2656897zbMATH OpenOpenAlexFDO

Authors Jakub Przybyło, Andrzej Żak

Publication date 17 March 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.37236/8376

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

\(t\)-node fault tolerant graphlargest component of a graph

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Review text

Summary: A graph \(G\) is called \(t\)-node fault tolerant with respect to \(H\) if \(G\) still contains a subgraph isomorphic to \(H\) after removing any \(t\) of its vertices. The least value of \(|E(G)|-|E(H)|\) among all such graphs \(G\) is denoted by \(\Delta(t,H)\). We study fault tolerance with respect to some natural architectures of a computer network, i.e. the \(d\)-dimensional toroidal grids and the hypercubes. We provide the first non-trivial lower bounds for \(\Delta(1,H)\) in these cases. For this aim we establish a general connection between the notion of fault tolerance and the size of a largest component of a graph. In particular, we give for all values of \(k\) (and \(n)\) a lower bound on the order of the largest component of any graph obtained from \(C_n\Box C_n\) via removal of \(k\) of its vertices, which is in general optimal.

Recommendations

• A flexible framework for fault tolerance in the grid
• A new fault-tolerance framework for grid computing
• Large fault-tolerant interconnection networks

Cites work

• (H,k) stable graphs with minimum size
• A Graph Model for Fault-Tolerant Computing Systems
• A survey of integrity
• Asymptotic Bounds on the Integrity of Graphs and Separator Theorems for Graphs
• Explicit construction of linear sized tolerant networks
• scientific article; zbMATH DE number 26495 (Why is no real title available?)
• scientific article; zbMATH DE number 1256708 (Why is no real title available?)
• On Minimum Fault-Tolerant Networks
• On sparse graphs with dense long paths
• The integrity of a cubic graph
• Two results about the hypercube

Cited in

(4)

• Transformation of grids to 1-fault-tolerant graphs
• Function of structural fault tolerance and d-limited connected component of CS graph
• A note on the integrity of grids
• k-fault-tolerant graphs for p disjoint complete graphs of order c

This page was built for publication: Largest component and node fault tolerance for grids

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