Fault Tolerance of Flower Snarks Under Subgraph Failures

Abstract

Fault tolerance is one of the most important criteria for evaluating the reliability of interconnection networks. Unlike classical connectivity measures that consider only individual vertex failures, structural fault models capture the failure of subnetworks and provide a more realistic assessment of network robustness. In this paper, we investigate the fault tolerance of the Flower snark through the notions of structure connectivity and substructure connectivity. For a connected graph $G$ and a subgraph $H$ of $G$, the $H$-structure connectivity (respectively, the $H$-substructure connectivity) of $G$ is the minimum cardinality of a set $\mathcal{H}$ of subgraphs of $G$, each of which is isomorphic to $H$ (respectively, a connected subgraph of $H$), such that the deletion of $\mathcal{H}$ disconnects $G$ or leaves a single vertex. We determine exact values of the $ H $-structure connectivity and $ H $-substructure connectivity of the Flower snark for $ H\in\{K_1,K_{1,r}\} $ where $ r\in\{1,2,3\} $.

Keywords

• fault tolerance
• structure connectivity
• substructure connectivity
• flower snark

References

1. [1] L. Ba and C. Bai, Structure connectivity of a class of Cayley graph, Int. J. Comput. Math. Comput. Syst. Theory, 10(1–2) (2025), 1–12.
2. [2] C¸ .S. Bilgit and C. C¸ iftc¸i, Connectivity and super connectivity of flower snark, submitted, (2026).
3. [3] F.T. Boesch, Synthesis of reliable networks—a survey, IEEE Trans. Reliab., 35(3) (1986), 240–246.
4. [4] G. Boruzanlı Ekinci, The super-connectivity of the double vertex graph of complete bipartite graphs, Fundam. J. Math. Appl., 4(4) (2021), 251–257.
5. [5] G. Brinkmann, J. Goedgebeur, J. H¨agglund and K. Markstr¨om, Generation and properties of snarks, J. Combin. Theory Ser. B, 103(4) (2013), 468–488.
6. [6] C.N. Campos, S. Dantas and C.P. de Mello, The total-chromatic number of some families of snarks, Discrete Math., 311(12) (2011), 984–988.
7. [7] F. C¸ elik, C. C¸ iftc¸i and F. Say, Connectivity and super connectivity of Goldberg snark, J. Supercomput., 82(672) (2026), 1–15.
8. [8] M. Ghebleh, S. Norine, R. Thomas et al., The circular chromatic index of flower snarks, Electron. J. Combin., (2006), N20.

9. [9] R. Hao, J. Niu, X. Wang, C.-Q. Zhang and T. Zhang, A note on Berge–Fulkerson coloring, Discrete Math., 309(13) (2009), 4235–4240.
10. [10] R. Isaacs, Infinite families of nontrivial trivalent graphs which are not Tait colorable, Amer. Math. Monthly, 82(3) (1975), 221–239.
11. [11] Y. Lei and J. Meng, Structure fault-tolerance of arrangement graphs, Appl. Math. Comput., 381 (2020), 125287.
12. [12] C. Li, S. Lin and S. Li, Structure connectivity and substructure connectivity of star graphs, Discrete Appl. Math., 284 (2020), 472–480.
13. [13] C.-K. Lin, L. Zhang, J. Fan and D. Wang, Structure connectivity and substructure connectivity of hypercubes, Theoret. Comput. Sci., 634 (2016), 97–107.
14. [14] Y. Lv, J. Fan, D.F. Hsu and C.-K. Lin, Structure connectivity and substructure connectivity of k-ary n-cube networks, Inform. Sci., 433 (2018), 115–124.
15. [15] D. Ma, H. Zhu and J. He, λ-numbers of several classes of snarks, J. Combin. Optim., 28(4) (2014), 787–799.
16. [16] Z. Maksimovic, J. Kratica, A. Savic and M. Bogdanovic, Some static Roman domination numbers for flower snarks, in XIII Balkan Conference on Operational Research Proceedings, (2018), 9–15.
17. [17] M. T¨urkmen, C. C¸ iftc¸i and G. Boruzanlı Ekinci, Structure and substructure connectivity of folded divide-and-swap cube, J. Supercomput., 81(4) (2025), 1–19.
18. [18] C.A. Weffort-Santos, C.N. Campos and R.C.S. Schouery, On gap-labellings of some families of graphs, Discrete Appl. Math., 340 (2023), 296–314.
19. [19] C. Zhao and H. Liu, Connected and tree domination on Goldberg and flower snarks, Appl. Math. Sci., 10(62) (2016), 3057–3064.
20. [20] Q. Zhou, S. Zhou, J. Liu and X. Liu, Structure and substructure connectivity of divide-and-swap cube, Theoret. Comput. Sci., 880 (2021), 20–36.