Geodesic
$k$-fault-tolerant graphs for $p$ disjoint complete graphs of order $c$
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1471-1484

Voir la notice de l'article provenant de la source Library of Science

Vertex-fault-tolerance was introduced by Hayes in 1976, and since then it has been systematically studied in different aspects. In this paper, we study graphs of order cp+k that are k-vertex-fault-tolerant for p disjoint complete graphs of order c, i.e., graphs in which removing any k vertices leaves a graph that has p disjoint complete graphs of order c as a subgraph. In this paper, we analyze some properties of such graphs for any value of k. The main contribution is to describe such graphs that have the smallest possible number of edges for k=1, p ≥ 1, and c ≥ 3.
Keywords: fault-tolerance, interconnection network, factor, algorithm, $k$-critical graph 
@article{DMGT_2024_44_4_a12,
     author = {Cichacz, Sylwia and G\H{o}rlich, Agnieszka and Suchan, Karol},
     title = {$k$-fault-tolerant graphs for $p$ disjoint complete graphs of order $c$},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1471--1484},
     publisher = {mathdoc},
     volume = {44},
     number = {4},
     year = {2024},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a12/}
}
TY  - JOUR
AU  - Cichacz, Sylwia
AU  - Gőrlich, Agnieszka
AU  - Suchan, Karol
TI  - $k$-fault-tolerant graphs for $p$ disjoint complete graphs of order $c$
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 1471
EP  - 1484
VL  - 44
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a12/
LA  - en
ID  - DMGT_2024_44_4_a12
ER  - 
%0 Journal Article
%A Cichacz, Sylwia
%A Gőrlich, Agnieszka
%A Suchan, Karol
%T $k$-fault-tolerant graphs for $p$ disjoint complete graphs of order $c$
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 1471-1484
%V 44
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a12/
%G en
%F DMGT_2024_44_4_a12
Cichacz, Sylwia; Gőrlich, Agnieszka; Suchan, Karol. $k$-fault-tolerant graphs for $p$ disjoint complete graphs of order $c$. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1471-1484. http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a12/