On the reliability of modified bubble-sort graphs

Document Type : Research Paper


Department of Mathematics, Urmia University, P. O. Box 57135 Urmia, Iran


The modified bubble-sort graph $MB_n$ $(n \geq 2)$ has been known as a topology structure of interconnection networks‎. ‎In this paper‎, ‎we propose simple method for arc-transitivity of $MB_n$ $(n \geq 2)$‎. ‎Also by using this result we investigate some reliability measures‎, ‎including‎ ‎super-connectivity‎, ‎cyclic edge connectivity‎, ‎etc.‎, ‎in the modified bubble-sort graphs‎.


Main Subjects

[1] F. T. Boesch and R. Tindell, Circulant and their connectivities, J. Graph Theory, 8 (1984) 487–499.
[2] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, Elsevier North Holland, 1976.
[3] E. Cheng and L. Lipták, Fault resiliency of Cayley graphs generated by transpositions, Int. J. Found. Comput. Sci.,
18 (2007) 1005–1022.
[4] Y. C. Chen, J. J. M. Tan and L. H. Hsu, Super-connectivity and super-edge-connectivity for some interconnection
networks, Appl. Math. Comput., 140 (2003) 245–254.
[5] A. Esfahanian and S. Hakimi, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett., 27
(1988) 195–199.
[6] M. Ghasemi, Some results about the reliability of folded hypercubes, Bull. Malays. Math. Sci. Soc., 44 (2021)
[7] K. Kamyab, M. Ghasemi and R. Varmazyar, Super connectivity of lexicographic product graphs, accepted to Ars.
Combin., arXive:2009.04831[math.GR].
[8] S. Lakshmivarahan, J. Jwo and S. K. Dhall, Symmetry in interconection networks based on Cayley graphs of
permutation groups, A Survey, Parall. Comput., 19 (1993) 361–407.
[9] Q. L. Li and Q. Li, Super edge connectivity properties of connected edge symmetric graphs, Networks, 33 (1999)
[10] M. Lü, G. L. Chen and J.-M. Xu, On super edge-connectivity of cartesian product graphs, Networks, 49 (2007)
[11] J. Meng, Connectivity of vertex and edge transitive graphs, Discrete Appl. Math., 127 (2003) 601–613.
[12] J. P. Ou, m-Restricted edge connectivity of graphs and network reliability, Department of Mathematics, Xiamen
University, 2003.
[13] J. P. Ou, Edge cuts leaving components of order at least m, Discrete Math., 305 (2005) 365–371.
[14] M. D. Plummer, On the cyclic connectivity of planar graphs, Lecture Notes in Math., 303 (1972) 235–242.
[15] H. Tarakmi, H. Azanchilar, M. Ghasemi and Gh. Azadi, n-restricted edge connectivity of m-barrel fullerene graphs,
Iran J. Sci. Technol Trans. A. Sci., 45 (2021) 997–1004.
[16] Y. Tian and J. Meng, On super restricted edge-connetctivity of edge-transitive graphs, Discrete Math., 310 (2010)
[17] R. Tindell, Connectivity of Cayley graphs, Combinatorial network theory, D. Z. Du and D. F. Hsu, eds, Kluwer
Academic publishers, (1996) 41–64.
[18] B. Wang and Z. Zhang, On the cyclic edge-connectivity of transitive graphs, Discrete Math., 309 (2009) 4555–4563.
[19] M. C. Yang, Super connectivity of balanced hypercubes, Appl. Math. Comput., 219 (2012) 970–975.
[20] C. Yang and J. Xu, Connectivity of lexicographic product and direct product of graphs, Ars. Combin., 111 (2013)
[21] Z. Zhang and J. Meng, On optimally-λ(3) transitive graphs, Discrete Appl. Math., 154 (2006) 1011–1018.
[22] Z. Zhang and B. Wang, Super cyclically edge-connected transitive graphs, J. Comb. Optim., 22 (2011) 549–562.
[23] J.-X. Zhou, Super-restricted edge-connectivity of regular edge-transitive graphs, Discrete Appl. Math., 160 (2012)
[24] J. X. Zhou, Atoms of cyclic edge connectivity in regular graphs, J. Comb. Optim, 31 (2014) 382–395.
[25] J. X. Zhou and Y. Q. Feng, Super-cyclically edge-connected regular graphs, J. Comb. Optim., 26 (2013) 393–411.
[26] J. X. Zhou, Z. L. Wu, S. C. Yang and K. W. Yuan, Symmetric property and reliability of balanced hypercubes,
IEEE Trans. Computers, 64 (2015) 876–881.