Article in volume
Authors:
Title:
On conditional connectivity of the Cartesian product of cycles
PDFSource:
Discussiones Mathematicae Graph Theory 43(1) (2023) 17-34
Received: 2020-02-05 , Revised: 2020-07-01 , Accepted: 2020-07-06 , Available online: 2020-08-24 , https://doi.org/10.7151/dmgt.2348
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 $H - F$ is a disconnected graph of minimum degree at least $h.$ Let
$G$ be the Cartesian product of $r\geq 1$ cycles, each of length at least four
and let $h$ be an integer such that $0\leq h\leq 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
References:
- 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 - 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 - 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 - 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 - 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 - F. Harary, Conditional connectivity, Networks 13 (1983) 347–357.
https://doi.org/10.1002/net.3230130303 - J.-M. Xu, On conditional edge-connectivity of graphs, Acta Math. Appl. Sin. 16 (2000) 414–419.
https://doi.org/10.1007/BF02671131 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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
Close