YE Liangcheng, LIANG Jiarong. On Conditional h-Vertex Connectivity of Some Networks[J]. Chinese Journal of Electronics, 2016, 25(3): 556-560. doi: 10.1049/cje.2016.05.023
Citation: YE Liangcheng, LIANG Jiarong. On Conditional h-Vertex Connectivity of Some Networks[J]. Chinese Journal of Electronics, 2016, 25(3): 556-560. doi: 10.1049/cje.2016.05.023

On Conditional h-Vertex Connectivity of Some Networks

doi: 10.1049/cje.2016.05.023
Funds:  This work is supported by the National Natural Science Foundation of China (No.61363002).
More Information
  • Corresponding author: LIANG Jiarong was born in 1966. He received the M.S. degree in applied mathematics from Northwestern Polytechnical University in 1995 and Ph.D. degree in institute of automation from South China University of Technology in 1998. He is a professor in School of Computer and Electronic Information, Guangxi University. His research interests are parallel and distributed, wireless sensor network and network reliability analysis. (Email:
  • Received Date: 2014-04-01
  • Rev Recd Date: 2014-07-07
  • Publish Date: 2016-05-10
  • The conditional h-vertex connectivity of G is defined as the minimum cardinality |S| (S ⊂V (G)) such that G-S is disconnected and has minimum degree at least h. It is an important measure of fault tolerance of networks. In this paper, we prove the lower bound of conditional hvertex connectivity of any n-dimensional hypercube-like network. We also determine the conditional h-vertex connectivity of Crossed cubes, Locally twisted cubes, Möbius cubes which are the members of hypercube-like networks.
  • loading
  • A.H. Esfahanian, "Generalized measures of fault tolerance with application to N-cube networks", IEEE Transactions on Computers, Vol.38, No.11, pp.1586-1591, 1989.
    S. Latifi, M. Hegde and M. Naraghi-Pour, "Conditional connectivity measures for large multiprocessor systems", IEEE Transactions on Computers, Vol.43, No.2, pp.218-222, 1994.
    F. Harary, "Conditional connectivity", Networks, Vol.13, No.3, pp.346-357, 1983.
    N.W. Chang, C.Y. Tsai and S.Y. Hsieh, "On 3-extra connectivity and 3-extra edge connectivity of folded hypercubes", IEEE Transactions on Computers, Vol.63, No.6, pp.1594-1600, 2014.
    W.S. Hong and S.Y. Hsieh, "Extra edge connectivity of hypercube-like networks", International Journal of Parallel, Emergent and Distributed Systems, Vol.28, No.2, pp.123-133, 2013.
    Q. Zhu, X.K.Wang and G. Cheng, "Reliability evaluation of BC networks", IEEE Transactions on Computers, Vol.62, No.11, pp.2337-2340, 2013.
    J. Xu, "On conditional edge-connectivity of graphs", Acta Mathematicae Applicatae Sinica, Vol.16, No.4, pp.414-419, 2000.
    A.D. Oh and H.A. Choi, "Generalized measures of fault tolerance in n-cube networks", IEEE Transactions on Parallel and Distributed Systems, Vol.4, No.6, pp.702-703, 1993.
    J. Wu and G. Guo, "Fault tolerance measures for m-ary ndimensional hypercubes based on forbidden faulty sets", IEEE Transactions on Computers, Vol.47, No.8, pp.888-893, 1998.
    X. Wang, J. Liang and Q. Dou, "Research on topological properties and embedding issues of the exchanged hypercube", Acta Electronica Sinica, Vol.40, No.4, pp.669-673, 2012. (in Chinese)
    X. Li and J. Xu, "Generalized measures of fault tolerance in (n, k)-star graphs",, 2012-4-6.
    X. Li and J. Xu, "Generalized measures of edge fault tolerance in (n, k)-star graphs", Mathematical Science Letters, Vol.1, No.2, pp.133-138, 2012.
    X. Li and J. Xu, "Generalized measures of fault tolerance in exchanged hypercubes", Information Processing Letters, Vol.113, No.14-16, pp.533-537, 2013.
    X.J. Li and J.M. Xu, "Edge-fault tolerance of hypercube-like networks", Information Processing Letters, Vol.113, No.19-21, pp.760-763, 2013.
    W. Yang, H. Li and J. Meng, "Conditional connectivity of Cayley graphs generated by transposition trees", Information Processing Letters, Vol.110, No.23, pp.1027-1030, 2010.
    Z. Zhang, W. Xiong and W. Yang, "A kind of conditional fault tolerance of alternating group graphs", Information Processing Letters, Vol.110, No.22, pp.998-1002, 2010.
    Y. Chen and J. Tan, "Restricted connectivity for three families of interconnection networks", Applied mathematics and computation, Vol.188, No.2, pp.1848-1855, 2007.
    M. Wan and Z. Zhang, "A kind of conditional vertex connectivity of star graphs", Applied Mathematics Letters, Vol.22, No.2, pp.264-267, 2009.
    A.S. Vaidya, P.S.N. Rao and S.R. Shankar, "A class of hypercube-like networks", Proceedings of 1993 5th IEEE Symposium on Parallel and Distributed Processing, pp.800-803, 1993.
    Y. Saad and M.H. Schultz, "Topological properties of hypercubes", IEEE Transactions on Computers, Vol.37, No.7, pp.867-872, 1988.
    K. Efe, "The crossed cube architecture for parallel computation", IEEE Transactions on Parallel and Distributed Systems, Vol.3, No.5, pp.513-524, 1992.
    P. Cull and S.M. Larson, "The Möbius cubes", IEEE Transactions on Computers, Vol.44, No.5, pp.647-659, 1995.
    X. Yang, D.J. Evans and G.M. Megson, "The locally twisted cubes", International Journal of Computer Mathematics, Vol.82, No.4, pp.401-413, 2005.
    J.H. Park, H.S. Lim and H.C. Kim, "Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements", Theoretical Computer Science, Vol.377, No.1- 3, pp.170-180, 2007.
    J. Fan and X. Jia, "Edge-pancyclicity and path-embeddability of bijective connection graphs", Information Sciences, Vol.178, No.2, pp.340-351, 2008.
    J. Fan, X. Jia, X. Liu, et al., "Efficient unicast in bijective connection networks with the restricted faulty node set", Information Sciences, Vol.181, No.11, pp.2303-2315, 2011.
    J. Fan and L. He, "BC connection networks and their properties", Chinese Journal of Computers, Vol.26, No.1, pp.84-90, 2003.
    D.B. West, Introduction to Graph Theory, Prentice hall, 2001.
  • 加载中


    通讯作者: 陈斌,
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (139) PDF downloads(986) Cited by()
    Proportional views


    DownLoad:  Full-Size Img  PowerPoint