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 LTQn, i.e., cλk+1(LTQn)=kn -exk/2 for 1 ≤ k ≤ 2[n/2], n ≥ 7, where exk=∑i=0s ti2ti +∑i=0s 2·i·2ti, and k is a positive integer with decomposition k=∑i=0s 2ti such that t0=⎣log2k⎦ and ti=⎣log2(k -∑r=0i-12tr)⎦ for i ≥ 1. As a by-product, we characterize the corresponding optimal solutions.
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
.
DOI: 10.1007/s40305-019-00259-8
[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)
