
doi: 10.37236/8376
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.
Graph labelling (graceful graphs, bandwidth, etc.), Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), largest component of a graph, \(t\)-node fault tolerant graph
Graph labelling (graceful graphs, bandwidth, etc.), Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), largest component of a graph, \(t\)-node fault tolerant graph
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
