The g-faulty-block connectivity of folded hypercubes
Springer Science and Business Media LLC - Trang 1-15 - 2024
Tóm tắt
There are some attacks on the network, such as botnet attack, DDoS attack and Local Area Network Denial attack, which are attacked on certain group of clustered nodes in the network. At present, the existing connectivity has certain defects in reflecting the fault-tolerant ability of the network under these network attacks. In order to measure the fault tolerance and reliability of a network which is attacked on certain group of clustered nodes in the network by attacker, Lin et al. (IEEE Trans Comput 70:1719–1731, 2021) proposed the g-faulty-block connectivity. A subset
$$F\subseteq V(G)$$
is called a g-faulty-block of a graph G if
$$G-F$$
is disconnected, each component of it has at least
$$g+1$$
vertices and the subgraph induced by F is connected. The cardinality of a minimum g-faulty-block of G, denoted by
$$\text{FB}\kappa _g(G)$$
, is the g-faulty-block connectivity of G. Larger h-fault block connectivity means that an attacker must launch an attack on a larger block of connected nodes so that each remaining component is not too small, which in turn limits the size of the larger components. The larger the h-fault block, the more difficult it is for an attacker to accomplish this goal. In this paper, we obtain
$$\text{FB}\kappa _0(\text{FQ}_n)=2n+1$$
,
$$\text{FB}\kappa _1(\text{FQ}_n)=3n-1$$
and
$$\text{FB}\kappa _g(\text{FQ}_n)=(g+2)n-3g+3$$
for
$$2\le g\le n-4$$
and
$$n\ge 7$$
, where
$$\text{FQ}_n$$
is n-dimension folded hypercube.
Tài liệu tham khảo
Bondy JA (2008) USR Murty Graph Theory. Springer-Verlag, Berlin
Boccaletti S et al (2006) Complex networks: structure and dynamics. Phys Rep 424:175–308
Cheng E, Lipták L, Yang W et al (2011) A kind of conditional vertex connectivity of Cayley graphs generated by 2-trees. Inf Sci 181(19):4300–4308
Chang NW, Hsieh SY (2013) Extroconnectivities of hypercube-like networks. J Comput Syst Sci 79:669–688
Chang NW, Tsai CY, Hsieh SY (2013) On 3-extra connectivity and 3-extra edge connectivity of folded hypercubes. IEEE Trans Comput 63(6):1594–1600
El-Amawy A, Latifi S (1991) Properties and performance of folded hypercubes. IEEE Trans Parallel Distrib Syst 2:31–42
Esmaeili T, Lak G, Rad AN (2012) 3D-FolH-NOC: a new structure for parallel processing and distributed systems. J Comput 4(6):163–168
Fàbrega J, Fiol MA (1994) Extra connectivity of graphs with large girth. Discrete Math 127:163–170
Fàbrega J, Fiol MA (1996) On the extra connectivity of graphs. Discrete Math 155:49–57
Guo J, Lu M (2016) The extra connectivity of bubble-sort star graphs. Theor Comput Sci 645:91–99
Han WP, Wang SY (2015) The \(g\)-extra conditional diagnosability of folded hypercubes. Appl Math Sci 9:346–357
Harary F (1983) Conditional connectivity. Netwworks 13:347–357
Lai CN, Chen GH, Duh DR (2002) Constructing one-to-many disjoint paths in folded hypercubes. IEEE Trans Comput 51:33–45
Larumbe F, Sansò B (2013) A tabu search algorithm for the location of data centers and software components in green cloud computing networks. IEEE Trans Cloud Comput 1:22–35
Lin L, Xu L, Zhou S (2015) Conditional diagnosability and strong diagnosability of split-star networks under the PMC model. Theor Comput Sci 562:565–580
Lin LM, Huang YZ, Wang DJ, Hsieh SY et al (2021) A novel measurement for network reliability. IEEE Trans Comput 70:1719–1731
Lin L et al (2016) Trustworthiness-hypercube-based reliable communication in mobile social networks. Inf Sci 369:34–50
Latifi S (1991) Simulation of PM21 network by folded hypercube. IEE Proc E Comput Digit Tech 138(6):397–400
Li X, Zhou S, Guo X et al (2021) The h-restricted connectivity of the generalized hypercubes. Theor Comput Sci 850:135–147
Li XJ, Xu JM (2013) Generalized measures of fault tolerance in exchanged hypercubes. Inf Process Lett 113(14–16):533–537
Park JS, Davis NJ (2001) The folded hypercube ATM switches. Proc IEEE Int Conf Netw Part II:370–379
Park JS, Davis NJ (2001) Modeling the folded hypercube ATM switches. In: The Proceedings of OPNETWORK
Wu J, Wang Y (2012) Social feature-based multi-path routing in delay tolerant networks. IEEE INFOCOM Conf 131:1368–1376
Wu J, Wang Y (2014) Hypercube-based multipath social feature routing in human contact networks. IEEE Trans Comput 63:383–396
Xu JM, Ma M (2006) Cycles in folded hypercubes. Appl Math Lett 19:140–145
Xu JM, Zhu Q, Hou XM, Zhou T (2005) On restricted connectivity and extra connectivity of hypercubes and folded hypercubes. J Shanghai Jiaotong Univ (Sci) 10(E–2):208–212
Yang W, Li H, Meng J (2010) Conditional connectivity of Cayley graphs generated by transposition trees. Inf Process Lett 110(23):1027–1030
Yang WH, Meng JX (2009) Extraconnectivity of hypercubes. Appl Math Lett 22:887–891
Yang WH, Zhao SL, Zhang SR (2017) Strong Menger connectivity with conditional faults of folded hypercubes. Inf Process Lett 125:30–34
Zhang MM, Zhou JX (2015) On \(g\)-extra connectivity of folded hypercubes. Theor Comput Sci 593:146–153
Zhu Q, Xu J, Hou X et al (2007) On reliability of the folded hypercubes. Inf Sci 177:1782–1788
Zhu Q, Zhang X (2017) The \(h\)-extra conditional diagnosability of hypercubes under the \(PMC\) model and \(MM^*\) model. Int J Comput Math Comput Syst Theory 1(1–4):141–150
Zaman S, He X (2022) Relation between the inertia indices of a complex unit gain graph and those of its underlying graph. Linear Multilinear A 2 70(5):843–877