On Conditional <em>h</em>-Vertex Connectivity of Some Networks

YE Liangcheng; LIANG Jiarong

doi:10.1049/cje.2016.05.023

Volume 25 Issue 3

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2016 > 25(3): 556-560

YE Liangcheng and LIANG Jiarong, “On Conditional h-Vertex Connectivity of Some Networks,” Chinese Journal of Electronics, vol. 25, no. 3, pp. 556-560, 2016, doi: 10.1049/cje.2016.05.023

Citation:

YE Liangcheng and LIANG Jiarong, “On Conditional h-Vertex Connectivity of Some Networks,” Chinese Journal of Electronics, vol. 25, no. 3, pp. 556-560, 2016, doi: 10.1049/cje.2016.05.023

YE Liangcheng and LIANG Jiarong, “On Conditional h-Vertex Connectivity of Some Networks,” Chinese Journal of Electronics, vol. 25, no. 3, pp. 556-560, 2016, doi: 10.1049/cje.2016.05.023

Citation:

YE Liangcheng and LIANG Jiarong, “On Conditional h-Vertex Connectivity of Some Networks,” Chinese Journal of Electronics, vol. 25, no. 3, pp. 556-560, 2016, doi: 10.1049/cje.2016.05.023

PDF( 973 KB)

On Conditional h-Vertex Connectivity of Some Networks

doi: 10.1049/cje.2016.05.023

School of Computer Science and Electronic Information, Guangxi University, Nanning 530004, China

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: gxuliangjr@163.com)
Received Date: 2014-04-01
Rev Recd Date: 2014-07-07
Publish Date: 2016-05-10

Abstract

Abstract

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.
- Hypercube-like networks,
- Fault tolerance,
- Conditional connectivity,
- Crossed cubes,
- Möbius cubes,
- Locally twisted cubes

FullText(HTML)

References(28)

References

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", http://arxiv.org/abs/1204.1440, 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.

Relative Articles

Supplements(0)

Cited By

Proportional views