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 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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},
     year = {2024},
     volume = {44},
     number = {4},
     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
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
%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/

[1] M. Ajtai, N. Alon, J. Bruck, R. Cypher, C.T. Ho, M. Naor and E. Szemerédi, Fault tolerant graphs, perfect hash functions and disjoint paths, in: Proc. 33rd Annual Symposium on Foundations of Computer Science, (IEEE 1992) 693–702. https://doi.org/10.1109/SFCS.1992.267781

[2] N. Alon and F.R.K. Chung, Explicit construction of linear sized tolerant networks, Discrete Math. 72 (1988) 15–19. https://doi.org/10.1016/j.disc.2006.03.025

[3] A. Brandstädt, V.B. Le and J.P. Spinrad, Graph Classes: A Survey (SIAM, 1999). https://doi.org/10.1137/1.9780898719796

[4] J. Bruck, R. Cypher and C.T. Ho, Fault-Tolerant Parallel Architectures with Minimal Numbers of Spares (IBM Research Report, 1991).

[5] S. Cichacz and K. Suchan, Minimum k-critical bipartite graphs, Discrete Appl. Math. 302 (2021) 54–66. https://doi.org/10.1016/j.dam.2021.06.005

[6] R. Diestel, Graph Theory (Grad. Texts in Math., Springer Nature, Berlin, 2017). https://doi.org/10.1007/978-3-662-53622-3

[7] A. Dudek, A. Szymański and M. Zwonek, (H, k)-stable graphs with minimum size, Discuss. Math. Graph Theory 28 (2008) 137–149. https://doi.org/10.7151/dmgt.1397

[8] S. Dutt and J.P. Hayes, Designing fault-tolerant systems using automorphisms, J. Parallel Distrib. Comput. 12 (1991) 249–268. https://doi.org/10.1016/0743-7315(91)90129-W

[9] O. Favaron, On k-factor-critical graphs, Discuss. Math. Graph Theory 16 (1996) 41–51. https://doi.org/10.7151/dmgt.1022

[10] J.P. Hayes, A graph model for fault-tolerant computing systems, IEEE Trans. Comput. C-25 (1976) 875–884. https://doi.org/10.1109/TC.1976.1674712

[11] L. Lovász, On the structure of factorizable graphs, Acta Math. Acad. Sci. Hungar. 23 (1972) 179–195. https://doi.org/10.1007/BF01889914

[12] Y. Lu, H. Salemi, B. Balasundaram and A. Buchanan, On fault-tolerant low-diameter clusters in graphs, INFORMS J. Comput. 34 (2022) 2867–3350. https://doi.org/10.1287/ijoc.2022.1231

[13] F. Mahdavi Pajouh, V. Boginski and E.L. Pasiliao, Minimum vertex blocker clique problem, Networks 64 (2014) 48–64. https://doi.org/10.1002/net.21556

[14] J. Przyby\l o and A. Żak, Largest component and node fault tolerance for grids, Electron. J. Combin. 28 (2021) #P1.44. https://doi.org/10.37236/8376

[15] T. Yamada and S. Ueno, Optimal fault-tolerant linear arrays, in: Proc. of the Fifteenth Annual ACM Symp. on Parallel Algorithms and Architectures, (ACM 2003) 60–64. https://doi.org/10.1145/777412.777423

[16] S. Ueno, A. Bagchi, S.L. Hakimi and E.F. Schmeichel, On minimum fault-tolerant networks, SIAM J. Discrete Math. 6 (1993) 565–574. https://doi.org/10.1137/0406044

[17] Q. Yu, Characterizations of various matching extensions in graphs, Australas. J. Combin. 7 (1993) 55–64.

[18] L. Zhang, Fault tolerant networks with small degree, in: Proc. of the Twelfth Annual ACM Symp. on Parallel Algorithms and Architectures, (ACM 2000) 64–69. https://doi.org/10.1145/341800.341809

[19] Z.-B. Zhang, X. Zhang, D. Lou and X. Wen, Minimum size of n-factor-critical graphs and k-extendable graphs, Graphs Combin. 28 (2012) 433–448. https://doi.org/10.1007/s00373-011-1045-y

[20] A. Żak, {On (Kq;k)-stable graphs}, J. Graph Theory 74 (2013) 216–221. https://doi.org/10.1002/jgt.21705

[21] A. Żak, A generalization of an independent set with application to (Kq;k)-stable graphs, Discrete Appl. Math. 162 (2014) 421–427. https://doi.org/10.1016/j.dam.2013.08.036