Conditional Edge Connectivity of the Locally Twisted Cubes

doi:10.1007/s40305-019-00259-8

Journal of the Operations Research Society of China ›› 2019, Vol. 7 ›› Issue (3): 501-509.doi: 10.1007/s40305-019-00259-8

Special Issue: Discrete optimization

Conditional Edge Connectivity of the Locally Twisted Cubes

Hui Shang, Eminjan Sabir, Ji-Xiang Meng

College of Mathematics and System Sciences, Xinjiang University, Urumqi 830046, China

Received:2018-11-21 Revised:2019-05-11 Online:2019-09-30 Published:2019-10-08
Contact: Ji-Xiang Meng, Hui Shang, Eminjan Sabir E-mail:mjxxju@sina.com;hui_shang1218@163.com;eminjan20150513@163.com

Abstract

Abstract: The k-component edge connectivity cλ_k(G) of a non-complete graph G is the minimum number of edges whose deletion results in a graph with at least k components. In this paper, we extend some results by Guo et al. (Appl Math Comput 334:401-406, 2018) by determining the component edge connectivity of the locally twisted cubes LTQ_n, i.e., cλ_k+1(LTQ_n)=kn -ex_k/2 for 1 ≤ k ≤ 2^[n/2], n ≥ 7, where ex_k=∑_i=0^s t_i2^t_i +∑_i=0^s 2·i·2^tⁱ, and k is a positive integer with decomposition k=∑_i=0^s 2^t_i such that t₀=⎣log₂k⎦ and t_i=⎣log₂(k -∑_r=0^i-12^t_r)⎦ for i ≥ 1. As a by-product, we characterize the corresponding optimal solutions.

Key words: Fault tolerance, Locally twisted cubes, Component edge connectivity

CLC Number:

05C40

Hui Shang, Eminjan Sabir, Ji-Xiang Meng. Conditional Edge Connectivity of the Locally Twisted Cubes[J]. Journal of the Operations Research Society of China, 2019, 7(3): 501-509.

TrendMD

References

[1] Guo, L., Su, G., Lin, W., Chen, J.:Fault tolerance of locally twisted cubes. Appl. Math. Comput. 334, 401-406(2018)
[2] Harary, F.:Conditional connectivity. Networks 13, 347-357(1983)
[3] Latifi, S., Hegde, M., Pour, M.N.:Conditional connectivity measures for large multiprocessor systems. IEEE Trans. Comput. 43, 218-222(1994)
[4] Sampathkumar, E.:Connectivity of a graph-a generalization. J. Comb. Inf. Syst. Sci. 9, 71-78(1984)
[5] Guo, L.:Reliability analysis of hypercube networks and folded hypercube networks. WSEAS Trans. Math. 16, 331-338(2017)
[6] Zhao, S., Yang, W.:Component edge connectivity of the folded hypercube. arXiv:1803.01312vl[math.CO] (2018)
[7] Zhao, S., Yang, W.:Component edge connectivity of hypercubes. Int. J. Found. Comput. Sci. 29, 995-1001(2018)
[8] Bondy, J.A., Murty, U.S.R.:Graph Theory. Springer, New York (2008)
[9] Yang, X., Evans, D.J., Megson, G.M.:The locally twisted cubes. Int. J. Comput. Math. 82, 401-413(2005)
[10] Hsieh, S.-Y., Wu, C.-Y.:Edge-fault-tolerant Hamiltonicity of locally twisted cubes under conditional edge faults. J. Comb. Optim. 19, 16-30(2010)
[11] Hsieh, S.-Y., Huang, H.-W., Lee, C.-W.:{2, 3}-restricted connected of locally twisted cubes. Theor. Comput. Sci. 615, 78-90(2016)
[12] Hung, R.-W.:Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes. Theor. Comput. Sci. 412, 4747-4753(2011)
[13] Ma, M., Xu, J.-M.:Panconnectivity of locally twisted cubes. Appl. Math. Lett. 19, 673-677(2006)
[14] Pai, K.-J., Chang, J.-M.:Improving the diameters of completely independent spanning trees in locally twisted cubes. Inf. Process. Lett. 141, 22-24(2019)
[15] Ren, Y., Wang, S.:The tightly super 2-extra connectivity and 2-extra diagnosability of locally twisted cubes. J. Interconnect. Netw. 17, 1-18(2017)
[16] Wei, C.-C., Hsieh, S.-Y.:h-restricted connectivity of locally twisted cubes. Discret. Appl. Math. 217, 330-339(2017)
[17] Wei, Y.-L., Xu, M.:The g-good-neighbor conditional diagnosability of locally twisted cubes. J. Oper. Res. Soc. China 6, 333-347(2018)
[18] Wang, M., Ren, Y., Lin, Y., Wang, S.:The tightly super 3-extra connectivity and diagnosability of locally twisted cubes. Am. J. Comput. Math. 7, 127-144(2017)
[19] Zhang, M., Meng, J., Yang, W., Tian, Y.:Reliability analysis of bejective connection networks in terms of the extra edge-connectivity. Inf. Sci. 279, 374-382(2014)
[20] Yang, W., Lin, H.:Reliability evaluation of BC networks in terms of the extra vertex-and edgeconnectivity. IEEE Trans. Comput. 63, 2540-2547(2014)
[21] Katseff, H.:Incomplete hypercubes. IEEE Trans. Comput. 37, 604-608(1988)

Conditional Edge Connectivity of the Locally Twisted Cubes

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 1

Recommended Articles

Metrics

Comments