1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

On Conditional Connectivity of the Cartesian Product of Cycles

Published Online: 29 Sep 2020
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 05 Feb 2020
Accepted: 06 Jul 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

The conditional h-vertex (h-edge) connectivity of a connected graph H of minimum degree k > h is the size of a smallest vertex (edge) set F of H such that HF is a disconnected graph of minimum degree at least h. Let G be the Cartesian product of r ≥ 1 cycles, each of length at least four and let h be an integer such that 0 ≤ h ≤ 2r − 2. In this paper, we determine the conditional h-vertex-connectivity and the conditional h-edge-connectivity of the graph G. We prove that both these connectivities are equal to (2rh)arh, where arh is the number of vertices of a smallest h-regular subgraph of G.

Keywords

MSC 2010

[1] Y.M. Borse and S.R. Shaikh, On 4-regular 4-connected bipancyclic subgraphs of hypercubes, Discrete Math. Algorithms Appl. 9 (2017) 1750032. doi:10.1142/S179383091750032X10.1142/S179383091750032XSearch in Google Scholar

[2] X.-B. Chen, Panconnectivity and edge-pancyclicity of multidimensional torus networks, Discrete Appl. Math. 178 (2014) 33–45. doi:10.1016/j.dam.2014.06.02110.1016/j.dam.2014.06.021Search in Google Scholar

[3] A.D. Oh and H.-A. Choi, Generalized measures of fault tolerence in n-cube networks, IEEE Trans. Parallel Distrib. Syst. 4 (1993) 702–703. doi:10.1109/71.24215310.1109/71.242153Search in Google Scholar

[4] A.-H. Esfahanian, Generalized measures of fault tolerance with application to N-cube networks, IEEE Trans. Comput. 38 (1989) 1586–1591. doi:10.1109/12.4213110.1109/12.42131Search in Google Scholar

[5] A.-H. Esfahanian and S.L. Hakimi, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett. 27 (1988) 195–199. doi:10.1016/0020-0190(88)90025-710.1016/0020-0190(88)90025-7Search in Google Scholar

[6] F. Harary, Conditional connectivity, Networks 13 (1983) 347–357. doi:10.1002/net.323013030310.1002/net.3230130303Search in Google Scholar

[7] J.-M. Xu, On conditional edge-connectivity of graphs, Acta Math. Appl. Sin. 16 (2000) 414–419. doi:10.1007/BF0267113110.1007/BF02671131Search in Google Scholar

[8] F.T. Leighton, Arrays and trees, Introduction to Parallel Algorithms and Architectures (Morgan Kaufmann, San Mateo, CA, 1992) 1–276. doi:10.1016/B978-1-4832-0772-8.50005-410.1016/B978-1-4832-0772-8.50005-4Search in Google Scholar

[9] S. Latifi, M. Hegde and M. Naraghi-Pour, Conditional connectivity measures for large multiprocessor systems, IEEE Trans. Comput. 43 (1994) 218–222. doi:10.1109/12.26212610.1109/12.262126Search in Google Scholar

[10] X.-J. Li and J.-M. Xu, Edge-fault tolerance of hypercube-like networks, Inform. Process. Lett. 113 (2013) 760–763. doi:10.1016/j.ipl.2013.07.01010.1016/j.ipl.2013.07.010Search in Google Scholar

[11] X.-J. Li, Y.-N. Guan, Z. Yan and J.-M. Xu, On fault tolerance of (n, k)-star networks, Theoret. Comput. Sci. 704 (2017) 82–86. doi:10.1016/j.tcs.2017.08.00410.1016/j.tcs.2017.08.004Search in Google Scholar

[12] S. Lin, S. Wang and C. Li, Panconnectivity and edge-pancyclicity of k-ary n-cubes with faulty elements, Discrete Appl. Math. 159 (2011) 212–223. doi:10.1016/j.dam.2010.10.01510.1016/j.dam.2010.10.015Search in Google Scholar

[13] W. Ning, The h-connectivity of exchanged crossed cube, Theoret. Comput. Sci. 696 (2017) 65–68. doi:10.1016/j.tcs.2017.07.02310.1016/j.tcs.2017.07.023Search in Google Scholar

[14] C.-C. Wei and S.-Y. Hsieh, h-restricted connectivity of locally twisted cubes, Discrete Appl. Math. 217 (2017) 330–339. doi:10.1016/j.dam.2016.08.01210.1016/j.dam.2016.08.012Search in Google Scholar

[15] M. Xu, J.-M. Xu, X.-M. Hou, Fault diameter of Cartesian product graphs, Inform. Process. Lett. 93 (2005) 245–248. doi:10.1016/j.ipl.2004.11.00510.1016/j.ipl.2004.11.005Search in Google Scholar

[16] L. Ye and J. Liang, On conditional h-vertex connectivity of some networks, Chinese J. Electron. 25 (2016) 556–560. doi:10.1049/cje.2016.05.02310.1049/cje.2016.05.023Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo