On component connectivity of hierarchical star networks. (English) Zbl 1505.68033
Summary: For an integer \(\ell\geq2\), the \(\ell \)-component connectivity of a graph \(G\), denoted by \(\kappa_\ell(G)\), is the minimum number of vertices whose removal from \(G\) results in a disconnected graph with at least \(\ell\) components or a graph with fewer than \(\ell\) vertices. This naturally generalizes the classical connectivity of graphs defined in term of the minimum vertex-cut. This kind of connectivity can help us to measure the robustness of the graph corresponding to a network. The hierarchical star networks \(H S_n\), proposed by Shi and Srimani, is a new level interconnection network topology, and uses the star graphs as building blocks. In this paper, by exploring the combinatorial properties and fault-tolerance of \(H S_n\), we study the \(\ell \)-component connectivity of hierarchical star networks \(H S_n\). We obtain the results: \( \kappa_3(H S_n)=2n-2\), \(\kappa_4(H S_n)=3n-3\) and \(\kappa_5(H S_n)=4n-5\) for \(n\geq5\).
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C40 | Connectivity |
| 68M15 | Reliability, testing and fault tolerance of networks and computer systems |
Keywords:
interconnection networks; component connectivity; generalized connectivity; hierarchical star networksReferences:
| [1] | Akers, S. B., Krishnamurthy, B. and Harel, D., The star graph: An attractive alternative to the \(n\)-cube, in Proc. Int’l. Conf. Parallel Process. (1987), pp. 393-400. |
| [2] | Chang, J.-M.et al., Two kinds of generalized \(3\)-connectivities of alternating group networks, in Proc. 12th International Frontiers of Algorithmics Workshop (FAW 2018), Guangzhou, China, , May 8-10, 2018, , pp. 12-23. |
| [3] | Chartrand, G.et al., Generalized connectivity in graphs, Bull. Bombay Math. Colloq.2 (1984) 1-6. |
| [4] | Cheng, E. and Lipman, M. J., Increasing the connectivity of the star graphs, Networks40(3) (2002) 165-169. · Zbl 1018.05055 |
| [5] | Cheng, E., Qiu, K. and Shen, Z., Connectivity results of hierarchical cubic networks as associated with linearly many faults, in Proc. Int. Symp. Pervasive Systems, Algorithms, and Networks (I-SPAN 2014), Chengdu, China, , December 19-21, 2014, pp. 1213-1220. |
| [6] | Cheng, E., Qiu, K. and Shen, Z., Connectivity results of complete cubic networks as associated with linearly many faults, J. Interconnec. Networks15 (2015) 155007. |
| [7] | Cheng, E., Qiu, K. and Shen, Z., Structural properties of generalized exchanged hypercubes, in Emergent Computation: Emergence, Complexity, Computation, ed. Adamatzky, A., Vol. 24 (Springer, Cham, 2017), pp. 215-232. · Zbl 1396.68078 |
| [8] | Feng, Y.-Q., Automorphism groups of Cayley graphs on symmetric groups with generating transposition sets, J. Comb. Theory Ser. B.96 (2006) 67-72. · Zbl 1079.05037 |
| [9] | Guo, C.et al., BCube: A high performance, server-centric network architecture for modular data centers, in Proc. ACM SIGCOMM9, Barcelona, Spain, , August 17, 2009, pp. 63-74. |
| [10] | Guo, C.et al., DCell: A scalable and fault-tolerant network structure for data centers, in Proc. ACM SIGCOMM, Seattle, WA, , August 17, 2008, pp. 75-86. |
| [11] | Gu, M.-M., Hao, R.-X. and Jiang, L., Fault-tolerance and diagnosability of hierarchical star networks, Int. J. Comput. Math. Comput. Sys. Theor.3(2) (2018) 106-121. |
| [12] | Hsu, L.-H.et al., Component connectivity of the hypercubes, Int. J. Comput. Math.89 (2012) 137-145. · Zbl 1238.05218 |
| [13] | Kavianpour, A., Sequential diagnosability of star graphs, Comput. Electr. Eng.22(1) (1996) 37-44. |
| [14] | Sampathkumar, E., Connectivity of a graph — A generalization, J. Combin. Inform. Sys. Sci.9 (1984) 71-78. · Zbl 0629.05043 |
| [15] | Shi, W. and Srimani, P. K., Hierachical star: A new two level interconnection network, J. Sys. Architecture51 (2005) 1-14. |
| [16] | Shi, W. and Srimani, P. K., Leader election in hierarchical star network, J. Parallel Distrib. Comput.65 (2005) 1435-1442. · Zbl 1101.68353 |
| [17] | Wu, R.-Y.et al., Node-disjoint paths in hierarchical hypercube networks, Inform. Sci.177 (2007) 4200-4207. · Zbl 1126.68016 |
| [18] | Wu, R.-Y.et al., Finding cycles in hierarchical hypercube networks, Inform. Process. Lett.109 (2008) 112-115. · Zbl 1191.68060 |
| [19] | Yang, X.et al., Largest connected component of a star graph with faulty vertices, Int. J. Comput. Math.85(12) (2008) 1771-1778. · Zbl 1151.05323 |
| [20] | Zhao, S., Yang, W. and Zhang, S., Component connectivity of hypercubes, Theoret. Comput. Sci.640 (2016) 115-118. · Zbl 1345.68242 |
| [21] | Zhou, S.et al., The \(t/k\)-diagnosability of star graph networks, IEEE Trans. Comput.64(2) (2015) 547-555. · Zbl 1360.68182 |
| [22] | Zheng, S. and Zhou, S., Diagnosability of the incomplete star graphs, Tsinghua Sci. Technol.177(8) (2007) 1771-1781. |
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.
