DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

S. Cichacz

Sylwia Cichacz

Faculty of Applied Mathematics, AGHUniversity of Science and TechnologyAl. Mickiewicza 3030-059 Kraków POLAND

email: cichacz@agh.edu.pl

0000-0002-7738-0924

A. Gőrlich

Agnieszka Gőrlich

email: forys@agh.edu.pl

K. Suchan

Karol Suchan

$Universidad Diego Portales, Santiago

email: karol.suchan@mail.udp.cl

0000-0003-0793-0924

Title:

$k$-fault-tolerant graphs for $p$ disjoint complete graphs of order $c$

PDF

Source:

Discussiones Mathematicae Graph Theory 44(4) (2024) 1471-1484

Received: 2023-01-08 , Revised: 2023-06-20 , Accepted: 2023-06-20 , Available online: 2023-07-14 , https://doi.org/10.7151/dmgt.2504

Abstract:

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 \geq 1$, and $c \geq 3$.

Keywords:

fault-tolerance, interconnection network, factor, algorithm, $k$-critical graph

References:

  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 $(K_q;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 $(K_q;k)$-stable graphs, Discrete Appl. Math. 162 (2014) 421–427.
    https://doi.org/10.1016/j.dam.2013.08.036
Close