Geodesic
On conditional connectivity of the Cartesian product of cycles
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 17-34 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

The conditional h-vertex (h-edge) connectivity of a connected graph H of minimum degree k gt;h is the size of a smallest vertex (edge) set F of H such that H - F 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 (2r-h)a_h^r, where a_h^r is the number of vertices of a smallest h-regular subgraph of G.
Keywords: fault tolerance, hypercube, conditional connectivity, cut, Cartesian product 
@article{DMGT_2023_43_1_a1,
     author = {Saraf, J.B. and Borse, Y.M. and Mundhe, Ganesh},
     title = {On conditional connectivity of the {Cartesian} product of cycles},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {17--34},
     year = {2023},
     volume = {43},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a1/}
}
TY  - JOUR
AU  - Saraf, J.B.
AU  - Borse, Y.M.
AU  - Mundhe, Ganesh
TI  - On conditional connectivity of the Cartesian product of cycles
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 17
EP  - 34
VL  - 43
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a1/
LA  - en
ID  - DMGT_2023_43_1_a1
ER  - 
%0 Journal Article
%A Saraf, J.B.
%A Borse, Y.M.
%A Mundhe, Ganesh
%T On conditional connectivity of the Cartesian product of cycles
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 17-34
%V 43
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a1/
%G en
%F DMGT_2023_43_1_a1
Saraf, J.B.; Borse, Y.M.; Mundhe, Ganesh. On conditional connectivity of the Cartesian product of cycles. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 17-34. http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a1/

[1] Y.M. Borse and S.R. Shaikh, On 4-regular 4-connected bipancyclic subgraphs of hypercubes, Discrete Math. Algorithms Appl. 9 (2017) 1750032. https://doi.org/10.1142/S179383091750032X

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

[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. https://doi.org/10.1109/71.242153

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

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

[6] F. Harary, Conditional connectivity, Networks 13 (1983) 347–357. https://doi.org/10.1002/net.3230130303

[7] J.-M. Xu, On conditional edge-connectivity of graphs, Acta Math. Appl. Sin. 16 (2000) 414–419. https://doi.org/10.1007/BF02671131

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

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

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

[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. https://doi.org/10.1016/j.tcs.2017.08.004

[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. https://doi.org/10.1016/j.dam.2010.10.015

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

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

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

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