Node connectivity and arc connectivity of a fuzzy graph. (English) Zbl 1233.05163

The fuzzy graph approach is more powerful in cluster analysis than the usual graph-theoretic approach due to its ability to handle the strengths of arcs effectively. It is shown that the minimum and maximum degree can be represented by only node strength in a complete fuzzy graph in Section 3 of this paper. In Section 4, the authors introduce the concept of node-strength sequence and study four classes of node-strength sequences of complete fuzzy graphs with respect to minimum and maximum strong degree. Two new connectivity parameters in fuzzy graphs, namely fuzzy node connectivity (\(\kappa (G)\)) and fuzzy arc connectivity (\(\kappa'(G)\)) of a connected fuzzy graph \(G\) are introduced in Sections 5 and Section 6, respectively. Fuzzy node cut, fuzzy arc cut and fuzzy bond are defined in Sections 5 and 6, too. Fuzzy bond is a special type of a fuzzy bridge. It is proved that at least one of the end nodes of a fuzzy bond is a fuzzy cut-node. In Section 7, the authors obtain the fuzzy analogue of Whitney’s theorem as follows: \(\kappa (G)\leq \kappa {^{\prime }}(G)\leq \delta_S(G)\), where \(\delta_S(G)\) is the minimum strong degree of fuzzy graph \(G\). It is shown that \(\kappa (G)=\kappa'(G)\) for a fuzzy tree and it is the minimum of the strengths of its strong arcs. The relationships of the new parameters with already existing vertex and edge connectivity parameters are studied and it is shown that the values of all these parameters are equal in a complete fuzzy graph in Section 8. Also a new clustering technique based on fuzzy arc connectivity is introduced in Section 9.


05C72 Fractional graph theory, fuzzy graph theory
05C40 Connectivity
03E72 Theory of fuzzy sets, etc.
05C22 Signed and weighted graphs
Full Text: DOI


[1] Bhattacharya, P.; Suraweera, F., An algorithm to compute the max – min powers and a property of fuzzy graphs, Pattern recognition letters, 12, 413-420, (1991)
[2] Bhattacharya, P., Some remarks on fuzzy graphs, Pattern recognition letters, 6, 297-302, (1987) · Zbl 0629.05060
[3] Bhutani, K.R., On automorphisms of fuzzy graphs, Pattern recognition letters, 9, 159-162, (1989) · Zbl 0800.68740
[4] Bhutani, K.R.; Rosenfeld, A., Strong arcs in fuzzy graphs, Information sciences, 152, 319-322, (2003) · Zbl 1040.03518
[5] Bhutani, K.R.; Rosenfeld, A., Fuzzy end nodes in fuzzy graphs, Information sciences, 152, 323-326, (2003) · Zbl 1040.03519
[6] Bhutani, K.R.; Rosenfeld, A., Geodesics in fuzzy graphs, Electronic notes in discrete mathematics, 15, 51-54, (2003)
[7] Mordeson, J.N.; Nair, P.S., Fuzzy graphs and fuzzy hypergraphs, (2000), Physica-Verlag · Zbl 0905.68095
[8] Nagoor Gani, A.; Basheer Ahamed, M., Order and size in fuzzy graph, Bulletin of pure and applied sciences, 22E, 1, 145-148, (2003) · Zbl 1068.05066
[9] Rosenfeld, A., Fuzzy graphs, (), 77-95
[10] Banerjee, Saibal, An optimal algorithm to find the degrees of connectedness in an undirected edge – weighted graph, Pattern recognition letters, 12, 421-424, (1991)
[11] Sameena, K.; Sunitha, M.S., Strong arcs and maximum spanning trees in fuzzy graphs, International journal of mathematical sciences, 5, 1, 17-20, (2006) · Zbl 1128.05310
[12] Sameena, K.; Sunitha, M.S., Characterisation of g-self centered fuzzy graphs, The journal of fuzzy mathematics, 16, 4, (2008) · Zbl 1185.05049
[13] K. Sameena, M.S. Sunitha, Distance in fuzzy graphs, Ph.D. Thesis, National Institute of Technology Calicut, India, 2008. · Zbl 1185.05049
[14] Mathew, Sunil; Sunitha, M.S., Types of arcs in a fuzzy graph, Information sciences, 179, 1760-1768, (2009) · Zbl 1200.05122
[15] Sunitha, M.S.; Vijayakumar, A., A characterization of fuzzy trees, Information sciences, 113, 293-300, (1999) · Zbl 0935.05084
[16] Sunitha, M.S.; Vijayakumar, A., Blocks in fuzzy graphs, The journal of fuzzy mathematics, 13, 1, 13-23, (2005) · Zbl 1065.05093
[17] M.S. Sunitha, A. Vijayakumar, Some metric aspects of fuzzy graphs, in: R. Balakrishna, H.M. Mulder, A. Vijayakumar (Eds), Proceedings of the Conference on Graph Connections, CUSAT, Allied Publishers, 1999, pp. 111-114. · Zbl 0957.05101
[18] Sunitha, M.S.; Vijayakumar, A., Complement of a fuzzy graph, Indian journal of pure and applied mathematics, 33, 9, 1451-1464, (2002) · Zbl 1013.05081
[19] Tong, Z.; Zheng, D., An algorithm for finding the connectedness matrix of a fuzzy graph, Congr. numer., 120, 189-192, (1996) · Zbl 0899.05065
[20] Xu, J., The use of fuzzy graphs in chemical structure research, (), 249-282
[21] Yeh, R.T.; Bang, S.Y.; relations, Fuzzy, Fuzzy relations, fuzzy graphs and their applications to clustering analysis, (), 125-149
[22] Yener, B.; Gunduz, C.; Gultekin, S.H., The cell graphs of cancer, Bioinformatics, 20, 1, 145-151, (2004)
[23] Zadeh, L.A., Fuzzy sets, Information and control, 8, 338-353, (1965) · Zbl 0139.24606
[24] Zadeh, L.A., Toward a generalized theory of uncertainty (GTU) - an outline, Information sciences, 172, 1-2, 1-40, (2005) · Zbl 1074.94021
[25] Zadeh, L.A., Is there a need for fuzzy logic?, Information sciences, 178, 13, 2751-2779, (2008) · Zbl 1148.68047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.