AUTHORS: Litao Guo

Download as PDF

ABSTRACT: A network is often modeled by a graph G VE = (, ) with the vertices representing nodes such as processors or stations, and the edges representing links between the nodes. One fundamental consideration in the design of networks is reliability. Let G be a connected graph and P be graph-theoretic property. The conditional connectivity λ(,) G P or κ(,) G P is the minimum cardinality of a set of edges or vertices, if it exists, whose deletion disconnects G and each remaining component has property P . Let F be a vertex set or edge set of G and P be the property of G F− with at least r components. Then we have r -component connectivity ( ) r c G κ and the r -component edge connectivity ( ) r c G λ . In this paper, we determine the r - component edge connectivity of hypercubes and folded hypercubes.

KEYWORDS: Reliability; Conditional connectivity; Cut; Networks; Component; Graph

REFERENCES:

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

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

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

[4] A. El-Amawy, S. Latifi, Properties and performance of folded hypercubes, IEEE Trans. Parallel Distrib. Syst. , Vol. 2, 1991, pp. 31 - 42.

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

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

[7] S. Hsieh, Extra edge connectivity of hypercube-like networks, Int. J. Parallel Emergent Distrib. Syst., Vol. 28, 2013, pp. 123-133.

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

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

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

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

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

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

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

[15] X. Yang, D. J. Evans, B. Chen, G. M. Megson, H. Lai, On the maximal connected component of hypercube with faulty vertices. Int. J. Comp. Math., Vol. 81, 2004, pp. 515-525.

[16] X. Yang, Fault tolerance of hypercube with forbidden faulty sets. Proc. 10th Chinese Conf. Fault-Tolerant Computing. Peking, 2003, pp. 135-139.

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

[18] 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, Vol. 36, 2006, pp. 246 - 253.

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

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

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