Largest component and node fault tolerance for grids (Q2656897)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Largest component and node fault tolerance for grids
scientific article

    Statements

    Largest component and node fault tolerance for grids (English)
    0 references
    0 references
    0 references
    17 March 2021
    0 references
    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.
    0 references
    \(t\)-node fault tolerant graph
    0 references
    largest component of a graph
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references