Bounds for neighbor connectivity of Cayley graphs generated by trees and unicyclic graphs

Mohamad Abdallah

Abstract


The neighbor connectivity refers to the minimum number of vertices whose removal, along with their neighbors, causes a previously connected graph to become disconnected. In this paper we focus on Cayley graphs constructed from the symmetric group Sn. We investigate the bounds of the neighbor connectivity for two cases: when the generating graph is a tree, and when it is a unicyclic graph with a unique cycle of length m, specifically considering cases where m = 3, m = n - 1, or m = n.

Keywords


neighbor connectivity, Cayley graph, interconnection networks

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2024.12.2.13

References

Y-Chuang Chen, Jimmy J.M. Tan, Lih-Hsing Hsu, and Shin-Shin Kao. Super-connectivity and super- edge-connectivity for some interconnection networks. Applied Mathematics and Computation, 140:245– 254, 2003.

E. Cheng, M.J. Lipman, and H. Park. Super connectivity of star graphs, alternating group graphs and split-stars. ARS Combinatoria, 59:107–116, 2001.

E. Cheng and L. Lipt ́ak. Fault resiliency of cayley graphs generated by transpositions. International Journal of Foundations of Computer Science, 18(5):1005–1022, 2007.

E. Cheng and L. Lipt ́ak. Linearly many faults in cayley graphs generated by transposition trees. Infor- mation Sciences, 177:4877–4882, 2007.

W.S. Chiue and B.S. Shieh. On connectivity of the cartesian product of two graphs. Journal of Applied Mathematics and Computation, 102:129–137, 1999.

W. A. Stein et al. Sage Mathematics Software (Version 9.6). The Sage Development Team, http://www.sagemath.org.

J-S. Fu. Conditional fault-tolerant hamiltonicity of star graphs. Parallel Computing, 33(7-8):488–496, 2007.

G. Gunther. Neighbour-connectibity in regular graphs. Discrete Applied Mathematics, 11(233-243), 1985.

G. Gunther and B. Hartnell. On minimizing the effects of betrayals in a resistance movement. Proc. 8th Manitoba Conf. Numer. Math. Comp., pages 285–386, 1978.

G. Gunther and B. Hartnell. Optimal k-secure graphs. Discrete Applied Mathematics, 2:241–247, 1980.

Y. j. Shang, R.-X. Hao, and M.-M. Gu. Neighbor connectivity of two kinds of cayley graphs. Acta Mathematicae Applicatae Sinica, English Series, 34(2):386–397, 2018.

S. Lakshmivarahan, J. Jwo, and S.K. Dhall. Symmetry in interconnection networks based on cayley graphs of permutation groups: a survey. Parallel Computing, 19(361-407), 1993.

S. Lakshmivarahan, J-S. Jwo, and S.K Dhall. Symmetry in interconnection networks based on cayley graphs of permutation groups: A survey. Parallel Computing, 19(4):361–407, 1993.

C. Li, S. Lin, and S. Li. Structure connectivity and substructure connectivity of star graphs. Discrete Applied Mathematics, 284:472–480, 2020.

S. Li, J. Tu, and C. Yu. The generalized 3-connectivity of star graphs and bubble-sort graphs. Applied Mathematics and Computation, 274:41–46, 2016.

N. Wang, J. Meng, and Y. Tian. Reliability evaluation of modified bubble-sort graph networks based on structure fault pattern. Applied Mathematics and Computation, 430:127257, 2022.

D. B. West. Introduction to Graph Theory. Prentice Hall, 1996.

C.S. Yang, J.F. Wang, J.Y. Lee, and F.T. Boesch. Graph theoretic reliability analysis for the boolean cube networks. IEEE Transactions on Circuits and Systems, 35(9):1175–1179, 1988.

W. Yang, H. Li, and J. Meng. Conditional connectivity of cayley graphs generated by transposition trees. Information Processing Letters, 110:1027–1030, 2010.

X. Yu, X. Huang, and Z. Zhang. A kind of conditional connectivity of cayley graphs generated by unicyclic graphs. Information Sciences, 243:86–94, 2013.

H. Zhang, S. Zhou, X. Liu, and Z. Yu. Extra (component) connectivity and diagnosability of bubble sort networks. Theoretical Computer Science, 940(Part A):180–189, 2023.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats