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.
@article{10_37236_8376,
author = {Jakub Przyby{\l}o and Andrzej \.Zak},
title = {Largest component and node fault tolerance for grids},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {1},
doi = {10.37236/8376},
zbl = {1459.05214},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8376/}
}
TY - JOUR
AU - Jakub Przybyło
AU - Andrzej Żak
TI - Largest component and node fault tolerance for grids
JO - The electronic journal of combinatorics
PY - 2021
VL - 28
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/8376/
DO - 10.37236/8376
ID - 10_37236_8376
ER -
%0 Journal Article
%A Jakub Przybyło
%A Andrzej Żak
%T Largest component and node fault tolerance for grids
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/8376/
%R 10.37236/8376
%F 10_37236_8376
Jakub Przybyło; Andrzej Żak. Largest component and node fault tolerance for grids. The electronic journal of combinatorics, Tome 28 (2021) no. 1. doi: 10.37236/8376
