International Journal of Fuzzy Logic and Intelligent Systems 2020; 20(4): 316323
Published online December 25, 2020
https://doi.org/10.5391/IJFIS.2020.20.4.316
© The Korean Institute of Intelligent Systems
Tarasankar Pramanik^{1}, Sovan Samanta^{2}, and Madhumangal Pal^{3}
^{1}Department of Mathematics, Khanpur Gangche High School, Midnapore, 721201, India
^{2}Department of Mathematics, Tamralipta Mahavidyalaya, Tamluk, India
^{3}Department of Applied Mathematics with Oceanology and Computer Programming, Vidyasagar University, Midnapore, India
Correspondence to :
Sovan Samanta (ssamantavu@gmail.com)
This is an Open Access article distributed under the terms of the Creative Commons Attribution NonCommercial License (http://creativecommons.org/licenses/bync/3.0/) which permits unrestricted noncommercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
Intervalvalued fuzzy graphs (IVFGs) are a generalization of fuzzy graphs. In this article, the sum distance between vertices in an IVFG is introduced. This definition satisfies the metric properties. In addition, some important aspects related to eccentricity, radius, and diameter are proved. The necessary and sufficient conditions for a vertex to be eccentric are established. The relationship between eccentricities and the sum distance between two vertices is derived. An algorithm is presented to determine the sum distance between two vertices in intervalvalued fuzzy graphs. Furthermore, some related theorems for the complete IVFG are deduced.
Keywords: Sum distance, Eccentricity, Intervalvalued fuzzy graphs
Graph theory has vast applications in data mining, image segmentation, clustering, image capturing, networking, communication, planning, scheduling, etc. Similarly, modeling of network topologies can be done using the concept of a graph. In addition, paths, walks, and circuits are used to solve many problems, such as the traveling salesman problem, database design, and resource networking. These lead to the development of new algorithms and new theories that can be used in various applications.
Recently, graph theory has been used to represent all types of real system. However, science and technology are characterized by complex processes and phenomena for which complete information is not always available for any system. For such cases, mathematical models have been developed to handle various types of system containing elements of uncertainty. A large number of these models are based on fuzzy sets, which are an extension of the ordinary set theory. In many cases, some aspects of a graphtheoretic problem may be uncertain. In 1975, Zadeh [1] introduced the notion of intervalvalued fuzzy sets as an extension of fuzzy sets in which the values of the membership degrees are interval numbers instead of the single point. Rosenfeld [1] introduced the notation of fuzzy graphs in 1975, introducing the concept of μdistance in fuzzy graphs. Based on this μdistance, Bhattacharya [3] introduced the concepts of eccentricity and center in fuzzy graphs, and the properties of this metric were further studied by Sunitha and Vijayakumar [4]. Samanta and Pal [5] introduced different types of fuzzy graph, such as fuzzy tolerance graphs, fuzzy threshold graphs [6], fuzzy planar graphs [7], and fuzzy competition graphs [
In 2011, Akram and Dudec [20] defined the intervalvalued fuzzy graph (IVFG) and described operations on it. Rashmanlou and Pal [21] defined the
In this report, the sum distance between vertices of IVFGs is introduced. This definition satisfies the metric properties. In addition, different properties related to the definitions are established. The eccentricity, radius, and diameter are defined based on the sum distance. In addition, the sum distance between vertices of an intervalvalued complete fuzzy graph is deduced.
A graph
A fuzzy set [1]
A fuzzy graph [2]
An IVFG [20] is a pair
An IVFG
Let
Let
Let
Let
The independent strength [12] of an edge (
The distance between two vertices in a graph is the number of edges in the shortest path between them. In reality, the distance between two nodes is not a reflection of the nature of the paths. To capture the nature of a path, the distances measured in fuzzy graphs are more useful. There are a few types of distance available in the literature. Here, the distance between two vertices in an IVFG is given below. Herein,
Let
If
This definition of distance satisfies the following properties for an IVFG
(a)
(b)
(c)
The statement (c) is true; as in every path, one can find a reverse path with the same sum distance.
Let
Let
The aim is to introduce an algorithm to find the sum distance between two given vertices. To find the sum distance between two given vertices, the breadthfirst search (BFS) technique is used.
In this algorithm, the notations defined below are used
i)
ii)
iii)
iv)
v)
vi)
vii)
Algorithm SD(
( 
if 

= min{ 
end if. 
for each edge 



if 


end if; 
end for; 
end while; 
The Algorithm SD takes
Let the processor take unit time to perform a single instruction. Steps 1, 2, 3, and 4 take
The eccentricity, radius, and diameter of an IVFG are defined based on the sum distance as follows:
Let
The following example illustrates the definitions.
An IVFG
The following theorem describes the relation between radius and diameter for any IVFG.
For any connected IVFG
If all the edges of a path are independent strong, then the following condition is true.
Let
Let
Again, it is clear that
For every two vertices
Assume without loss of generality
This theorem can be further extended to the following one.
For every two adjacent vertices
Assume without loss of generality
For every two adjacent vertices
The necessary and sufficient condition of a vertex to be eccentric can be found from the following theorem.
Let
where
It is known that
Thus,
Conversely, let ∑_{(}
If
Let
where
Let, if possible, a vertex
In addition, if
If
Assume
This lemma is not sufficient. If all the vertices of an IVFG are eccentric, then the graph need not be selfcentered. In Figure 1, all vertices are eccentric, and the central vertices are only
Let
The proof of the theorem is obvious.
The sum distance for complete IVFG is deduced in the following theorem.
Let
Let
The sum of the distances between the vertices in an IVFG was described. This distance is not an interval but rather a real number. Depending on the distance, the eccentricity, radius, diameter, etc. were introduced. The relation between the radius and diameter and the eccentricities between any two vertices were established. The necessary and sufficient conditions for a vertex to be eccentric were derived. In addition, the condition of the vertices in a selfcentered IVFG was established. The definition of sum distance and other concepts were applied to a complete IVFG.
A technique was used empirically to determine the sum distance between vertices in an IVFG. An algorithm was also proposed to determine the sum distance. The BFS technique was used to determine the distance. Some other techniques can be used to define the sum distances. However, the method used is appropriate because the sum distance between vertices in an IVFG can be deduced as the sum distance between vertices in fuzzy graphs. This result is significant because an IVFG is the generalization of fuzzy graphs. The distance measured in this study should be helpful in capturing the real distances in any network. Based on this, network centrality can be defined.
Email: tarasankar.math07@gmail.com
Email: ssamantavu@gmail.com
Email: mmpalvu@gmail.com
International Journal of Fuzzy Logic and Intelligent Systems 2020; 20(4): 316323
Published online December 25, 2020 https://doi.org/10.5391/IJFIS.2020.20.4.316
Copyright © The Korean Institute of Intelligent Systems.
Tarasankar Pramanik^{1}, Sovan Samanta^{2}, and Madhumangal Pal^{3}
^{1}Department of Mathematics, Khanpur Gangche High School, Midnapore, 721201, India
^{2}Department of Mathematics, Tamralipta Mahavidyalaya, Tamluk, India
^{3}Department of Applied Mathematics with Oceanology and Computer Programming, Vidyasagar University, Midnapore, India
Correspondence to:Sovan Samanta (ssamantavu@gmail.com)
This is an Open Access article distributed under the terms of the Creative Commons Attribution NonCommercial License (http://creativecommons.org/licenses/bync/3.0/) which permits unrestricted noncommercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
Intervalvalued fuzzy graphs (IVFGs) are a generalization of fuzzy graphs. In this article, the sum distance between vertices in an IVFG is introduced. This definition satisfies the metric properties. In addition, some important aspects related to eccentricity, radius, and diameter are proved. The necessary and sufficient conditions for a vertex to be eccentric are established. The relationship between eccentricities and the sum distance between two vertices is derived. An algorithm is presented to determine the sum distance between two vertices in intervalvalued fuzzy graphs. Furthermore, some related theorems for the complete IVFG are deduced.
Keywords: Sum distance, Eccentricity, Intervalvalued fuzzy graphs
Graph theory has vast applications in data mining, image segmentation, clustering, image capturing, networking, communication, planning, scheduling, etc. Similarly, modeling of network topologies can be done using the concept of a graph. In addition, paths, walks, and circuits are used to solve many problems, such as the traveling salesman problem, database design, and resource networking. These lead to the development of new algorithms and new theories that can be used in various applications.
Recently, graph theory has been used to represent all types of real system. However, science and technology are characterized by complex processes and phenomena for which complete information is not always available for any system. For such cases, mathematical models have been developed to handle various types of system containing elements of uncertainty. A large number of these models are based on fuzzy sets, which are an extension of the ordinary set theory. In many cases, some aspects of a graphtheoretic problem may be uncertain. In 1975, Zadeh [1] introduced the notion of intervalvalued fuzzy sets as an extension of fuzzy sets in which the values of the membership degrees are interval numbers instead of the single point. Rosenfeld [1] introduced the notation of fuzzy graphs in 1975, introducing the concept of μdistance in fuzzy graphs. Based on this μdistance, Bhattacharya [3] introduced the concepts of eccentricity and center in fuzzy graphs, and the properties of this metric were further studied by Sunitha and Vijayakumar [4]. Samanta and Pal [5] introduced different types of fuzzy graph, such as fuzzy tolerance graphs, fuzzy threshold graphs [6], fuzzy planar graphs [7], and fuzzy competition graphs [
In 2011, Akram and Dudec [20] defined the intervalvalued fuzzy graph (IVFG) and described operations on it. Rashmanlou and Pal [21] defined the
In this report, the sum distance between vertices of IVFGs is introduced. This definition satisfies the metric properties. In addition, different properties related to the definitions are established. The eccentricity, radius, and diameter are defined based on the sum distance. In addition, the sum distance between vertices of an intervalvalued complete fuzzy graph is deduced.
A graph
A fuzzy set [1]
A fuzzy graph [2]
An IVFG [20] is a pair
An IVFG
Let
Let
Let
Let
The independent strength [12] of an edge (
The distance between two vertices in a graph is the number of edges in the shortest path between them. In reality, the distance between two nodes is not a reflection of the nature of the paths. To capture the nature of a path, the distances measured in fuzzy graphs are more useful. There are a few types of distance available in the literature. Here, the distance between two vertices in an IVFG is given below. Herein,
Let
If
This definition of distance satisfies the following properties for an IVFG
(a)
(b)
(c)
The statement (c) is true; as in every path, one can find a reverse path with the same sum distance.
Let
Let
The aim is to introduce an algorithm to find the sum distance between two given vertices. To find the sum distance between two given vertices, the breadthfirst search (BFS) technique is used.
In this algorithm, the notations defined below are used
i)
ii)
iii)
iv)
v)
vi)
vii)
Algorithm SD(
( 
if 

= min{ 
end if. 
for each edge 



if 


end if; 
end for; 
end while; 
The Algorithm SD takes
Let the processor take unit time to perform a single instruction. Steps 1, 2, 3, and 4 take
The eccentricity, radius, and diameter of an IVFG are defined based on the sum distance as follows:
Let
The following example illustrates the definitions.
An IVFG
The following theorem describes the relation between radius and diameter for any IVFG.
For any connected IVFG
If all the edges of a path are independent strong, then the following condition is true.
Let
Let
Again, it is clear that
For every two vertices
Assume without loss of generality
This theorem can be further extended to the following one.
For every two adjacent vertices
Assume without loss of generality
For every two adjacent vertices
The necessary and sufficient condition of a vertex to be eccentric can be found from the following theorem.
Let
where
It is known that
Thus,
Conversely, let ∑_{(}
If
Let
where
Let, if possible, a vertex
In addition, if
If
Assume
This lemma is not sufficient. If all the vertices of an IVFG are eccentric, then the graph need not be selfcentered. In Figure 1, all vertices are eccentric, and the central vertices are only
Let
The proof of the theorem is obvious.
The sum distance for complete IVFG is deduced in the following theorem.
Let
Let
The sum of the distances between the vertices in an IVFG was described. This distance is not an interval but rather a real number. Depending on the distance, the eccentricity, radius, diameter, etc. were introduced. The relation between the radius and diameter and the eccentricities between any two vertices were established. The necessary and sufficient conditions for a vertex to be eccentric were derived. In addition, the condition of the vertices in a selfcentered IVFG was established. The definition of sum distance and other concepts were applied to a complete IVFG.
A technique was used empirically to determine the sum distance between vertices in an IVFG. An algorithm was also proposed to determine the sum distance. The BFS technique was used to determine the distance. Some other techniques can be used to define the sum distances. However, the method used is appropriate because the sum distance between vertices in an IVFG can be deduced as the sum distance between vertices in fuzzy graphs. This result is significant because an IVFG is the generalization of fuzzy graphs. The distance measured in this study should be helpful in capturing the real distances in any network. Based on this, network centrality can be defined.
An intervalvalued fuzzy graph.
Algorithm SD(
( 
if 

= min{ 
end if. 
for each edge 



if 


end if; 
end for; 
end while; 
Table 1. Some important notations.
Names  Notations 

Intervalvalued fuzzy graphs  
Edge membership value  
Vertex membership value  
Distance  
Eccentricity  
Sum distance 
An intervalvalued fuzzy graph.