Structure connectivity and substructure connectivity of wheel networks. (English) Zbl 1464.68284
Summary: Consider a graph \(G\) and its connected subgraph \(T\). The \(T\)-structure connectivity \(\kappa(G; T)\) of \(G\) is the cardinality of a minimum set of subgraphs in \(G\), whose removal disconnects \(G\) and each element in the set is isomorphic to \(T\). The \(T\)-substructure connectivity \(\kappa^s(G; T)\) of \(G\) is the cardinality of a minimum set of subgraphs in \(G\), whose removal disconnects \(G\) and each element in the set is isomorphic to a connected subgraph of \(T\). In \(G\), the standard connectivity \(\kappa(G)\) is regarded as a simplification of both \(\kappa(G; T)\) and \(\kappa^s(G; T)\). The wheel network, denoted by \(C W_n\), is an attractive interconnected network prototype for multiple CPU systems. In this paper, we determine \(\kappa(C W_n; P_{2 k + 1})\) (resp. \( \kappa^s(C W_n; P_{2 k + 1})\)) for \(n \geq 5\) and \(k + 1 \leq 2 n - 4\), \(\kappa(C W_n; P_{2 k})\) (resp. \( \kappa^s(C W_n; P_{2 k})\)) for \(n \geq 6\) and \(k \leq 2 n - 4\) and a lower bound of \(\kappa(C W_n; C_{2 k})\) (resp. \( \kappa^s(C W_n; C_{2 k})\)) for \(n \geq 6\) and \(k \leq 2 n - 4\).
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C38 | Paths and cycles |
| 05C40 | Connectivity |
Keywords:
interconnected networks; structure connectivity; substructure connectivity; wheel networks; paths; cyclesReferences:
| [1] | Lin, C.-K.; Zhang, L.; Fan, J.; Wang, D., Structure connectivity and substructure connectivity of hypercubes, Theor. Comput. Sci., 634, 97-107 (2016) · Zbl 1339.68208 |
| [2] | Sabir, E.; Meng, J., Structure fault tolerance of hypercubes and folded hypercubes, Theor. Comput. Sci., 711, 44-55 (2018) · Zbl 1387.68188 |
| [3] | Lin, S.; Wang, S.; Li, C., Panconnectivity and edge-pancyclicity of k-ary n-cubes with faulty elements, Discrete Appl. Math., 159, 4, 212-223 (2011) · Zbl 1214.68087 |
| [4] | Stewart, I. A.; Xiang, Y., Embedding long paths in k-ary n-cubes with faulty nodes and links, IEEE Trans. Parallel Distrib. Syst., 19, 8, 1071-1085 (2008) |
| [5] | Wang, S.; Zhang, G.; Feng, K., Fault tolerance in k-ary n-cube networks, Theor. Comput. Sci., 460, 34-41 (2012) · Zbl 1252.68044 |
| [6] | Feng, K.; Wang, S.; Zhang, G., Link failure tolerance in the arrangement graphs, Int. J. Found. Comput. Sci., 26, 2, 241-254 (2015) · Zbl 1322.68025 |
| [7] | Wang, S.; Feng, K., Fault tolerance in the arrangement graphs, Theor. Comput. Sci., 533, 64-71 (2014) · Zbl 1358.68046 |
| [8] | Hsieh, S.-Y., Embedding longest fault-free paths onto star graphs with more vertex faults, Theor. Comput. Sci., 337, 1-3, 370-378 (2005) · Zbl 1104.68085 |
| [9] | Latifi, S., A study of fault tolerance in star graph, Inf. Process. Lett., 102, 5, 196-200 (2007) · Zbl 1184.68115 |
| [10] | Araki, T.; Kikuchi, Y., Hamiltonian laceability of bubble-sort graphs with edge faults, Inf. Sci., 177, 13, 2679-2691 (2007) · Zbl 1115.68106 |
| [11] | Li, S.; Tu, J.; Yu, C., The generalized 3-connectivity of star graphs and bubble-sort graphs, Appl. Math. Comput., 274, 41-46 (2016) · Zbl 1410.05108 |
| [12] | Chou, Z.-T.; Hsu, C.-C.; Sheu, J.-P., Bubble-sort star graphs: a new interconnection network, (Proceedings of the International Conference on Parallel and Distributed Systems (1996)), 41-48 |
| [13] | Cai, H.; Liu, H.; Lu, M., Fault-tolerant maximal local-connectivity on bubble-sort star graphs, Discrete Appl. Math., 181, 33-40 (2015) · Zbl 1304.05085 |
| [14] | Guo, J.; Lu, M., Conditional diagnosability of bubble-sort star graphs, Discrete Appl. Math., 201, 141-149 (2016) · Zbl 1329.05271 |
| [15] | Guo, J.; Lu, M., The extra connectivity of bubble-sort star graphs, Theor. Comput. Sci., 645, 91-99 (2016) · Zbl 1348.68021 |
| [16] | Zhang, G.; Wang, D., Structure connectivity and substructure connectivity of bubble-sort star graph networks, Appl. Math. Comput., 363, Article 124632 pp. (2019) · Zbl 1433.68062 |
| [17] | Chang, N.-W.; Hsieh, S.-Y., 2, 3-extraconnectivities of hypercube-like networks, J. Comput. Syst. Sci., 79, 5, 669-688 (2013) · Zbl 1268.68133 |
| [18] | Day, K., The conditional node connectivity of the k-ary n-cube, J. Interconnect. Netw., 5, 1, 13-26 (2004) |
| [19] | Gu, M.-M.; Hao, R.-X., 3-extra connectivity of 3-ary n-cube networks, Inf. Process. Lett., 114, 9, 486-491 (2014) · Zbl 1296.68110 |
| [20] | Hsieh, S.-Y.; Huang, H.-W.; Lee, C.-W., \(\{2, 3 \}\)-restricted connectivity of locally twisted cubes, Theor. Comput. Sci., 615, 78-90 (2016) · Zbl 1334.68025 |
| [21] | Latifi, S.; Hegde, M.; Naraghi-Pour, M., Conditional connectivity measures for large multiprocessor systems, IEEE Trans. Comput., 43, 2, 218-222 (1994) |
| [22] | Lv, Y.; Xiang, Y., The conditional connectivity of \((n, k)\)-star graph, Adv. Mater. Res., 433, 440, 4853-4856 (2012) |
| [23] | Wang, S.; Ma, X., The g-extra connectivity and diagnosability of crossed cubes, Appl. Math. Comput., 336, 60-66 (2018) · Zbl 1427.68028 |
| [24] | Yang, W.; Li, H.; Meng, J., Conditional connectivity of Cayley graphs generated by transposition trees, Inf. Process. Lett., 110, 23, 1027-1030 (2010) · Zbl 1379.05069 |
| [25] | Fàbrega, J.; Fiol, M. A., On the extraconnectivity of graphs, Discrete Math., 155, 1-3, 49-57 (1996) · Zbl 0857.05064 |
| [26] | Lv, Y.; Fan, J.; Hsu, D. F.; Lin, C.-K., Structure connectivity and substructure connectivity of k-ary n-cube networks, Inf. Sci., 433-434, 115-124 (2018) · Zbl 1436.68051 |
| [27] | Li, D.; Hu, X.; Liu, H., Structure connectivity and substructure connectivity of twisted hypercubes (2018) |
| [28] | Zhang, G.; Lin, S., Path and cycle fault tolerance of bubble-sort graph networks, Theor. Comput. Sci., 779, 8-16 (2019) · Zbl 1422.68200 |
| [29] | Akers, Sheldon B.; Krishnamurthy, Balakrishnan, A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput., 38, 4, 555-566 (1989) · Zbl 0678.94026 |
| [30] | Chou, Z.-T., Bubble-sort star graphs: a new interconnection network (1995), Department of Information Management, National Taiwan Institute of Technology, Master thesis |
| [31] | Shi, H.; Lu, J., On conjectures of interconnection networks, Comput. Eng. Appl., 44, 31, 112-115 (2008), (in Chinese) |
| [32] | Shi, H.; Hou, F.; Ma, J.; Wang, G., Study on diameter and average distance of wheel network, J. Gansu Sci., 24, 2, 103-106 (2012), (in Chinese) |
| [33] | Hou, F., Some New Results of the Wheel Networks and Bubble-Sort Star Networks[D] (2013), Northwest Normal University, (in Chinese) |
| [34] | Feng, W.; Jirimutu; Wang, S., The Nature Diagnosability of Wheel Graph Networks Under the PMC Model and MM^⁎ Model, Ars Comb., 143, 255-287 (2019) · Zbl 1463.94081 |
| [35] | You, L.; Han, Y., Structure connectivity and substructure connectivity of alternating group graphs, (2018 IEEE International Conference on Progress in Informatics and Computing (2018)), 317-321 |
| [36] | Zhang, G.; Wang, D., Structure connectivity and substructure connectivity of k-ary n-cube networks, IEEE Access, 7, 134496-134504 (2019) |
| [37] | Bondy, J. A.; Murty, U. S.R., Graph Theory (2007), Springer: Springer New York · Zbl 1134.05001 |
| [38] | Hungerford, Thomas W., Algebra (1974), Springer-Verlag: Springer-Verlag New York · Zbl 0293.12001 |
| [39] | Ren, Y.; Wang, S., Some properties of the g-good-neighbor (g-extra) diagnosability of a multiprocessor system, Am. J. Comput. Math., 6, 259-266 (2016) |
| [40] | Feng, W.; Wang, S., The 2-extra connectivity of wheel network, Math. Probl. Eng., 2020, 1-5 (2020) · Zbl 07345020 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
