High strength connectivity in fuzzy graphs

Mehdipoor, N.; Talebi, Y.

doi:10.47974/JDMSC-2410

Open Access Research Article

High strength connectivity in fuzzy graphs

^*N. MehdipoorCorresponding authornargesmehdipoor@yahoo.comDepartment of MathematicsUniversity of MazandaranBabolsar, 4741613534, Iran0000-0002-4858-483XView full profile → , Y. Talebitalebi@umz.ac.irDepartment of MathematicsUniversity of MazandaranBabolsar, 4741613534, Iran0000-0003-2311-4628View full profile →

* Corresponding author · click or hover a name for details

pp. 1–24Online FirstJuly 2026DOI: 10.47974/JDMSC-2410 Crossmark XML

Received:: 01 Jan 2025
Published Online:: 02 Jul 2026
Article type:: Research Article
Language:: EN
Article no.:: JDMSC-2410
Pages:: 1–24

Abstract

A minimum vertex-cut set of a connected fuzzy graph T = (V, E, κ, λ), abbreviated MVC, is a vertex-cut set with minimum cardinality. Let W be an MVC set of T. The strength of W is defined as the S(W) = max{min{λ(p, q)|q ∈ V\W}|p ∈ W}. The maximum value of the strength of all MVC sets of T = (V, E, κ, λ) is called high strength connectivity of graph T and represented by HS(T). In this article, the high strength connectivity of the vertex-cut set in famous fuzzy graphs was determined. Also, an algorithm was introduced to calculate high strength connectivity in these graphs by using Sage software. Examples of the high strength connectivity applications in economic and power plant were given.

Keywords

Vertex-cut Minimum vertex-cut Strengths High strength connectivity

Subject Classifications

05C72

References

[1] S. Ali, S. Mathew, J.N. Mordeson, and H. Rashmanlou, “Vertex connectivity of fuzzy graphs with applications to human trafficking,” New Mathematics and Natural Computation, vol. 14, no. 3, pp. 457-485 (2018). [Online]. Available: https://doi.org/10.1142/S1793005718500278.
[2] T.A. Al-Hawary, “ Density results for perfectly regular and perfectly edgeregular fuzzy graphs,” Journal of Discrete Mathematical Sciences and Cryptography, Vol. 26, , no. 2, pp. 521-528 (2023). [Online]. Available: https://doi.org/10.1080/09720529.2021.1961898.
[3] D. Bauer, F. Boesch, C. Suffel, and R. Tindell, “Connectivity extremal problems and the design of reliable probabilistic networks,” in The Theory and Application of Graphs, Wiley, New York, pp. 45-54 (1981).
[4] R.A. Beezer, Sage for Linear algebra. A Supplement to a first course in linear algebra, Sage web site https://www.sagemath.org (2011).
[5] T. Biedl and K. Murali, “On computing the vertex connectivity of 1-plane graphs,” arXiv:2212.06782 (2022).
[6] P. Bhattacharya, “Some remarks on fuzzy graphs,” Pattern Recognition Letters, vol. 6, no. 5, pp. 297-302 (1987). [Online]. Available: https://doi.org/10.1016/0167-8655(87)90012-2.
[7] F. Boesch and R. Tindell, “Circulants and their connectivities,” Journal of Graph Theory, vol. 8, pp. 487-499 (1984). [Online]. Available: https://doi.org/10.1002/jgt.3190080406.
[8] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Elsevier, Great Britain (1976).
[9] W.S. Chiue and B.S. Shieh, “On connectivity of the Cartesian product of two graphs,” Applied Mathematics and Computation, vol. 102, pp. 129-137 (1999). [Online]. Available: https://doi.org/10.1016/S0096-3003(98)10041-3.
[10] J. Edmonds and R.M. Karp,”Theoretical improvements in algorithmic efficiency for network flow problems,” Journal of the Association for Computing Machinery, vol. 19, no. 2, pp. 248-264 (1972). [Online]. Available: http://dx.doi.org/10.1145/321694.321699.
[11] A. Frank, Connections in combinatorial optimization, Oxford University Press (2011).
[12] A. Frank and T. Jordán, “Directed vertex-connectivity augmentation,” Mathematical Programming, vol. 84, pp. 537-553 (1999). [Online]. Available: https://andrasfrank.web.elte.hu/cikkek/FrankJ40.
[13] F. Harary, “Conditional connectivity,” Networks, vol. 13, pp. 346-357 (1983). [Online]. Available: https://doi.org/10.1002/net.3230130303.
[14] F. H¨orsch and Z. Szigeti,”Eulerian orientations and vertex-connectivity,” Discrete Applied Mathematics, vol. 289, pp. 115-124 (2021). [Online]. Available: https://doi.org/10.1016/j.dam.2020.09.022.
[15] D. Huang and Z. Zhang, On Cyclic vertex-connectivity of cartesian product digraphs, Springer-Verlag New York, Inc., New York, NY, USA (2012). [Online]. Available: doi: 10.1007/s10878-011-9395-1.
[16] B. Jackson and T. Jordán, “Independence free graphs and vertex connectivity augmentation,” Journal of Combinatorial Theory, Series B, vol. 94, no. 1, pp. 31-77 (2005). [Online]. Available: https://doi.org/10.1016/j.jctb.2004.01.004.
[17] A. Jain and B.V. Ramana Reddy, “A novel method of modeling wireless sensor network using fuzzy graph and energy efficient fuzzy based k-hop clustering algorithm,” Wireless Personal Communications, vol. 82, no. 1, pp. 157-181 (2015). [Online]. Available: https://doi.org/10.1007/s11277-014-2201-5.
[18] G.J. Klir and B. Yuan, Fuzzy sets and fuzzy logic: Theory and applications, Prentice Hall, Hoboken, NJ, USA (1997).
[19] A.N.A. Koam, M. Akram and P. Liu, “Decision-making analysis based on fuzzy graph structures,” Hindawi, Mathematical Problems in Engineering, pp. 1-30 (2010). [Online]. Available: doi:10.1155/2020/6846257.
[20] M. Manzano, K. Bilal, E. Calle and S.U. Khan, “On the connectivity of data center networks,” IEEE Communications Letters, vol. 17, no 11, pp. 2172-2175 (2013). [Online]. Available: doi:10.1109/lcomm.2013.091913.131176.
[21] S. Mathew, J.N. Mordeson and D.S. Malik, Fuzzy graph theory, Studies in Fuzziness and Soft Computing (2018).
[22] S. Mathew and M.S. Sunitha, “Node connectivity and arc connectivity in fuzzy graphs,” Information Sciences, vol. 180, pp. 519-531 (2010). [Online]. Available: https://doi.org/10.1016/j.ins.2009.10.006.
[23] J. Meng and Y. Ji, “On a kind of restricted edge connectivity of graphs,” Discrete Applied Mathematics, vol. 117, pp. 183-193 (2002). [Online]. Available: https://doi.org/10.1016/S0166-218X(00)00337-1.
[24] J.N. Mordeson and P. Chang-Shyh, “Operations on fuzzy graphs,” Information Science, vol. 79, pp. 159-170 (1994). [Online]. Available: https://doi.org/10.1016/0020-0255(94)90116-3.
[25] J.N. Mordeson and P.S. Nair, Fuzzy graph and fuzzy hypergraphs, Studies in fuzziness and soft computing, Physica-Verlag.46 (2000).
[26] V. Prabavathy and B. Preethika, “Twin proper neutrosophic fuzzy graphs,” Journal of Interdisciplinary Mathematics, vol. 27, no. 5, pp. 1109-1116 (2024). [Online]. Available: https://doi.org/10.47974/JIM-1939.
[27] A. Prabhath, S. Mathew and J.N. Mordeson, Generalized cycle connectivity in fuzzy graphs, Fuzzy sets and systems (2024).
[28] D. Qin, Y. Tian, L. Chen, and J. Meng, “Cyclic vertex-connectivity of Cartesian product graphs,” International Journal of Parallel, Emergent and Distributed Systems, vol. 35, pp. 81-90 (2020). [Online]. Available: doi: 10.1080/17445760.2019.1659259.
[29] A. Rosenfeld, “Fuzzy graphs,” in L.A. Zadeh, K.S. Fu, and M. Shimura, Eds., Fuzzy Sets and Their Applications, Academic Press, New York, pp. 77-95 (1975).
[30] S.H. Sadati and A.A. Talebi, “A description of connectivity indices in a cubic fuzzy graph with an application,” Journal of Multiple-Valued Logic and Soft Computing, vol. 40, no. 5-6, pp. 569-585 (2023).
[31] S.G. Shrinivas, S. Vertrivel, and N.M. Elango, “Applications of graph theory in computer science: An overview,” International Journal of Engineering Science and Technology, vol. 2, no. 9, pp. 610-621 (2010).
[32] R.T. Yeh and S.Y. Bang, “Fuzzy relations, fuzzy graphs, and their applications to clustering analysis,” in Fuzzy Sets and Their Applications to Cognitive and Decision Processes, pp. 125-149 (1975). [Online]. Available: doi:10.1016/B978-0-12-775260-0.50010-4.
[33] Z. Yu, Q. Liu, and Z. Zhang, “Cyclic vertex connectivity of star graphs,” in Proceedings of the International Conference on Combinatorial Optimization and Applications, vol. 3, pp. 433-442 (2011). [Online]. Available: doi:10.1007/978-3-642-17458-2−18.
[34] J.M. Xu, “On conditional edge-connectivity of graphs,” Acta Mathematica Sinica, vol. 16B, no. 4, pp. 414-419 (2000). [Online]. Available: oi:10.1007/BF02671131.
[35] J.M. Xu, Theory and application of graphs, Kluwer Academic Publishers, Dordrecht/Boston/London (2003).
[36] H.J. Yousif, A. Ameer and H.K. Sulaiman, “Cutoff fuzzy dominating set of strong fuzzy graph,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 28, no. 2, pp. 577-585 (2025). [Online]. Available: https://doi.org/10.47974/JDMSC-2260.
[37] L.A. Zadeh, “Fuzzy sets,” infection control, vol. 8, pp. 338-353 (1965). [Online]. Available: doi:10.1016/S0019-9958(65)90241-X.

Views: 195Downloads: 134Citations: 0