AUTHORS: Litao Guo

Download as PDF

ABSTRACT: Let G = (V, E) be a connected graph. A r-component cut of G is a set of vertices whose deletion results in a graph with at least r components. r-component connectivity cκr(G) of G is the size of the smallest r-component cut. The r-component edge connectivity cλr(G) can be defined similarly. In this paper, we determine the r-component (edge) connectivity of crossed cubes CQn for small r. And we also prove other properties of CQn.

KEYWORDS: Interconnection networks; Fault tolerance; r-component edge connectivity

REFERENCES:

[1] J. Bondy, U. Murty, Graph theory and its application, Academic Press, 1976.

[2] E. Cheng, L. Lesniak, M. Lipman, L. Lipta´k, Conditional matching preclusion sets, Information Sciences 179, 2009, pp. 1092- 1101.

[3] G. Chartrand, S. Kapoor, L. Lesniak, D. Lick, Generalized connectivity in graphs, Bull. Bombay Math. Colloq. 2, 1984, pp. 1-6.

[4] C. Chang, C. Wu, Conditional fault diameter of crossed cubes, J. Parallel Distrib. Comput. 69, 2009, pp. 91-99.

[5] E. Efe, The crossed cube architecture for parallel computing, IEEE Trans. Parallel Distrib. Systems 3 (5), 1992, pp. 513-524.

[6] K. Efe, P.K. Blackwell, W. Slough, T. Shiau, Topological properties of the crossed cube architecture,Parallel Computing 20, 1994, pp. 1763- 1775.

[7] J. Fabrega, M. Fiol, On the extraconnectivity of ´ graphs, Discr. Math. 155, 1996, pp. 49 - 57.

[8] J. Fan, Diagnosability of crossed cubes under the comparison diagnosis model, IEEE Transactions on Parallel and Distributed Systems 13 (10), 2002, pp. 1099-1104.

[9] J. Fan, X. Lin, X. Jia, Optimal path embedding in crossed cubes, IEEE Transactions on Parallel and Distributed Systems 16 (2), 2004, pp. 1190- 1200.

[10] J. Fan, X. Lin, X. Jia, Node-pancyclicity and edge-pancyclicity in crossed cubes, IEEE Transactions on Parallel and Distributed Systems 16 (2), 2004, pp. 1190-1200.

[11] L. Guo, X. Guo, Fault tolerance of hypercubes and folded hypercubes, J Supercomput. 68, 2014, pp. 1235-1240.

[12] L. Guo, Fault tolerance of hypercubes and folded hypercubes in terms of component connectivity , submitted.

[13] P. D. Kulasinghe, Connectivity of the crossed cube hypercubes, Inform. Processing Let. 61, 1997, pp. 221-226.

[14] S. Hsieh, Extra edge connectivity of hypercubelike networks, Int. J. Parallel Emergent Distrib. Syst. 28, 2013, pp. 123-133.

[15] L. Hsu, E. Cheng, L. Liptak, J. Tan, C. Lin, T. ´ Ho, Component connectivity of the hypercubes, Int. J. Comput. Math. 89, 2012, pp. 137-145.

[16] M. Lin, M. Chang, D. Chen, Efficient algorithms for reliability analysis of distributed computing systems, Inform. Sci. 117, 1999, pp. 89 - 106.

[17] L. Lin, L. Xu, S. Zhou, Relating the extra connectivity and the conditional diagnosability of regular graphs under the comparison model, Theoretical Comput. Sci. 618, 2016, pp. 21-29.

[18] M. Ma, J. Xu, Edge-pancyclicity of crossed cubes, J. China Univ. Sci. Tech. 35 (3), 2005, pp. 329-333.

[19] E. Sampathkumar, Connectivity of a graphła generalization, J. Comb. Inf. Syst. Sci. 9, 1984, pp. 71-78.

[20] J. Xu, Q. Zhu, X. Hou, T. Zhou, On restricted connectivity and extra connectivity of hypercubes and folded hypercubes, J. Shanghai Jiaotong Univ., Sci. 10(2), 2005, pp. 203-207.

[21] W. Yang, H. Li, On reliability of the folded hypercubes in terms of the extra edge-connectivity, Inform. Sci. 272, 2014, pp. 238-243.

[22] W. Yang, S. Zhao, S. Zhang, Strong Menger connectivity with conditional faults of folded hypercubes, Inform. Processing Let. 125, 2017, pp. 30-34.

[23] Q. Zhu, J. Xu, X. Hou, M. Xu, On reliability of the folded hypercubes, Inform. Sci. 177, 2007, pp. 1782 - 1788.

[24] Q. Zhu, J. Xu, On restricted edge connectivity and extra edge connectivity of hypercubes and foled hypercubes, J. University of Science and Technology of China 36(3), 2006, pp. 246 -253.

[25] S. Zhao, W. Yang, S. Zhang, Component connectivity of hypercubes, Theoretical Comput. Sci. 640, 2016, pp. 115-118.

[26] M. Zhang, J. Zhou, On g-extra connectivity of folded hypercubes, Theoretical Comput. Sci. 593, 2015, pp. 146-153.

[27] M. Zhang, L. Zhang, X. Feng, Reliability measures in relation to the h-extra edge-connectivity of folded hypercubes, Theoretical Comput. Sci. 615, 2016, pp. 71-77.