Advanced
DEGREE OF VERTICES IN VAGUE GRAPHS†
DEGREE OF VERTICES IN VAGUE GRAPHS†
Journal of Applied Mathematics & Informatics. 2015. Sep, 33(5_6): 545-557
Copyright © 2015, Korean Society of Computational and Applied Mathematics
  • Received : February 24, 2015
  • Accepted : April 14, 2015
  • Published : September 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
R.A. BORZOOEI
HOSSEIN RASHMANLOU

Abstract
A vague graph is a generalized structure of a fuzzy graph that gives more precision, flexibility and compatibility to a system when compared with systems that are designed using fuzzy graphs. In this paper, we define two new operation on vague graphs namely normal product and tensor product and study about the degree of a vertex in vague graphs which are obtained from two given vague graphs G 1 and G 2 using the operations cartesian product, composition, tensor product and normal product. These operations are highly utilized by computer science, geometry, algebra, number theory and operation research. In addition to the existing operations these properties will also be helpful to study large vague graph as a combination of small, vague graphs and to derive its properties from those of the smaller ones. AMS Mathematics Subject Classification : 05C99.
Keywords
1. Introduction
Graphs and hypergraphs have been applied in a large number of problemsincluding cancer detection, robotics, human cardiac functions, networking and designing. It was Zadeh [25] who introduced fuzzy sets and fuzzy logic into mathematics to deal with problems of uncertainty. As most of the phenomena around us involve much of ambiguity and vagueness, fuzzy logic and fuzzy math-ematics have to play a crucial role in modeling real time systems with some level of uncertainty. The most important feature of a fuzzy set is that a fuzzy set A is a class of objects that satisfy a certain (or several) property. Gau and Buehrer [5] proposed the concept of vague set in 1993, by replacing the value of an ele-ment in a set with a subinterval of [0,1]. Namely, a true-membership function tv ( x ) and a false membership function fv ( x ) are used to describe the boundaries of the membership degree. The initial definition given by Kaufmann [6] of a fuzzy graph was based on the fuzzy relation proposed by Zadeh [26] . Later Rosenfeld [15] introduced the fuzzy analogue of several basic graph-theoretic concepts. Mordeson and Nair [7] defined the concept of complement of fuzzy graph and studied some operations on fuzzy graphs. Akram et al. [2 , 3 , 4] introduced vague hypergraphs, certain types of vague graphs and regularity in vague intersection graphs and vague line graphs . Ramakrishna [9] introduced the concept of vague graphs and studied some of their properties. Pal and Rashmanlou [8] studied irregular interval-valued fuzzy graphs. Also, they de-fined antipodal interval-valued fuzzy graphs [10] , balanced interval-valued fuzzy graphs [11] , some properties of highly irregular interval-valued fuzzy graphs [12] and a study on bipolar fuzzy graphs [14] . Rashmanlou and Yang Bae Jun investigated complete interval-valued fuzzy graphs [13] . Samanta and Pal defined fuzzy tolerance graphs [16] , fuzzy threshold graphs [17] , fuzzy planar graphs [18] , fuzzy k -competition graphs and p -competition fuzzy graphs [19] , irregular bipolar fuzzy graphs [20] , fuzzy coloring of fuzzy graphs [21] . In this paper, we defined two new operation on vague graphs namely normal product and tensor product and studied about the degree of a vertex in vague graphs which are obtained from two given vague graphs G 1 and G 2 using the operations cartesian product, composition, tensor product and normal product. For further details, reader may look into [1 , 22 , 23 , 24] .
2. Preliminaries
By a graph G = ( V , E ), we mean a non-trivial, finite, connected and undirected graph without loops or multiple edges. Formally, given a graph G = ( V , E ), two vertices x , y V are said to be neighbors, or adjacent nodes, if xy E . A fuzzy subset μ on a set X is a map μ : X → [0,1]. A fuzzy binary relation on X is a fuzzy subset μ on X × X . A fuzzy graph G is a pair of functions G = ( σ , μ ) where σ is a fuzzy subset of a non-empty set V and μ : V × V → [0,1] is a symmetric fuzzy relation on σ , i.e. μ ( uv ) ≤ σ ( u ) ∧ σ ( v ). The degree of a vertex u in fuzzy graph G is defined by dG ( u ) = Σ u≠v μ ( uv ) = Σ uvE μ ( uv ). The order of a fuzzy graph G is defined by O ( G ) = Σ uV σ ( u ).
The main objective of this paper is to study of vague graph and this graph is based on the vague set defined below.
Definition 2.1 ( [5] ). A vague set on an ordinary finite non-empty set X is a pair ( tA , fA ), where tA : X → [0, 1], fA : X → [0, 1] are true and false membership functions, respectively such that 0 ≤ tA ( x )+ fA ( x ) ≤ 1, for all x X . Note that tA ( x ) is considered as the lower bound for degree of membership of x in A and fA ( x ) is the lower bound for negative of membership of x in A . So, the degree of membership of x in the vague set A is characterized by interval [ tA ( x ), 1− fA ( x )]. Let X and Y be ordinary finite non-empty sets. We call a vague relation to be a vague subset of X × Y , that is an expression R defined by
PPT Slide
Lager Image
where tR : X × Y → [0, 1], fR : X × Y → [0, 1], which satisfies the condition 0 ≤ tR ( x , y ) + fR ( x , y ) ≤ 1, for all ( x , y ) ∈ X × Y .
Definition 2.2 ( [9] ). Let G = ( V , E ) be a crisp graph. A pair G = ( A , B ) is called a vague graph on a crisp graph G = ( V , E ), where A = ( tA , fA ) is a vague set on V and B = ( tB , fB ) is a vague set on E V × V such that
PPT Slide
Lager Image
for each edge xy E .
If G is a vague graph, then the order of G is defined and denoted as
PPT Slide
Lager Image
and the size of G is
PPT Slide
Lager Image
The open degree of a vertex u in a vague graph G = ( A , B ) is defined as d ( u ) = dt ( u ), df ( u )) where
PPT Slide
Lager Image
If all the vertices have the same open neighborhood degree n , then G is called an n -regular vague graph.
Definition 2.3. Let G 1 = ( A 1 , B 1 ) and G 2 = ( A 2 , B 2 ) be two vague graphs of
PPT Slide
Lager Image
= ( V 1 , E 1 ) and
PPT Slide
Lager Image
= ( V 2 , E 2 ) respectively.
(1) The cartesian product G 1 × G 2 of G 1 and G 2 is defined as pair ( A 1 × A 2 , B 1 × B 2 ) such that
PPT Slide
Lager Image
PPT Slide
Lager Image
  • for allu∈V1andu2v2∈E2,
PPT Slide
Lager Image
  • for allz∈V2andu1v1∈E1.
(2) The composition G 1 G 2 of G 1 and G 2 is defined as pair ( A 1 A 2 , B 1 B 2 ) such that
PPT Slide
Lager Image
PPT Slide
Lager Image
  • for allu∈V1andu2v2∈E2,
PPT Slide
Lager Image
  • for allz∈V2andu1v1∈E1,
PPT Slide
Lager Image
  • for all (u1;u2)(v1;v2) ∈E◦−E,
where E = E ∪ {( u 1 , u 2 )( v 1 , v 2 ) | u 1 v 1 E 1 , u 2 v 2 }.
3. Degree of vertices in vague graphs
Operation in fuzzy graph is a great tool to consider large fuzzy graph as a combination of small fuzzy graphs and to derive its properties from those of the smaller ones. Also, they are conveniently used in many combinatorial applications. In various situations they present a suitable construction means. For example in partition theory we deal with complex objects. A typical such object is a fuzzy graph and a fuzzy hypergraph with large chromatic number that we do not know how to compute exactly the chromatic number of these graphs. In such cases, these operations have the main role in solving problems. Hence, in this section, at first we define two new operations on vague graphs namely normal product and tensor product. Then we study about the degree of a vertex in vague graphs which are obtained from two given vague graphs G 1 and G 2 using the operations cartesian product, composition, tensor product and normal product.
Definition 3.1. The normal product of two vague graphs Gi = ( Ai , Bi ) on Gi = ( Vi , Ei ), i = 1, 2 is defined as a vague graph ( A 1 A 2 , B 1 B 2 ) on G = ( V , E ) where V = V 1 × V 2 and E = {(( u , u 2 )( u , v 2 )) | u V 1 , u 2 v 2 E 2 } ∪ {(( u 1 , z )( v 1 , z )) | u 1 v 1 E 1 , z V 2 }∪{(( u 1 , u 2 )( v 1 , v 2 )) | u 1 v 1 E 1 , u 2 v 2 E 2 } such that.
PPT Slide
Lager Image
PPT Slide
Lager Image
  • for allu2V1andu2v22E2,
PPT Slide
Lager Image
  • for allz∈V2andu1v1∈E1,
PPT Slide
Lager Image
  • for allu1v1∈E1andu2v2∈E2.
Definition 3.2. The tensor product of two vague graphs Gi = ( Ai , Bi ) on Gi = ( Vi , Ei ), i = 1, 2, is defined as a vague graph ( A 1 A 2 , B 1 B 2 ) on G = ( V , E ) where V = V 1 × V 2 and E = {( u 1 , u 2 ), ( v 1 , v 2 ) | u 1 v 1 E 1 , u 2 v 2 E 2 } such that
PPT Slide
Lager Image
PPT Slide
Lager Image
  • for allu1v1∈E1andu2v2∈E2.
Now, we derive degree of a vertex in the cartesian product. By the definition of cartesian product for any vertex ( u 1 , u 2 ) ∈ V 1 × V 2 ,
PPT Slide
Lager Image
Theorem 3.3. Let G 1 = ( A 1 , B 1 ) and G 2 = ( A 2 , B 2 ) be two vague graphs . If t A1 t B2 , f A1 f B2 and t A2 t B1 , f A2 f B1 then
PPT Slide
Lager Image
Proof . From the definition of a vertex in the cartesian product we have
PPT Slide
Lager Image
Also we have
PPT Slide
Lager Image
Hence, d G1×G2 ( u 1 , u 2 ) = d G1 ( u 1 ) + d G2 ( u 2 ). □
Example 3.4. Consider the vague graphs G 1 , G 2 and G 1 × G 2 as follows.
Since t A1 t B2 , f A1 f B2 , t A2 t B1 and f A2 f B1 . By Theorem 3.3, we have
PPT Slide
Lager Image
So, d G1×G2 ( u 1 , u 2 ) = (0.5, 1.2).
PPT Slide
Lager Image
Hence, d G1×G2 ( u 1 , v 2 ) = (0.5, 1.2).
Similarly, we can find the degrees of all the vertices in G 1 × G 2 . This can be verified in the Figure 1 .
PPT Slide
Lager Image
Cartesian product of G1 and G2
Now we calculate the degree of a vertex in composition. By the definition of composition for any vertex ( u 1 , u 2 ) ∈ V 1 × V 2 we have
PPT Slide
Lager Image
Theorem 3.5. Let G 1 = ( A 1 , B 1 ) and G 2 = ( A 2 , B 2 ) be two vague graphs. If t A1 t B2 , f A1 f B2 , t A2 t B1 and f A2 f B1 , then d G1G2 ( u 1 , u 2 ) = | V 2 | d G1 ( u 1 ) + d G2 ( u 2 ) for all ( u 1 , u 2 ) ∈ V 1 × V 2 .
Proof .
PPT Slide
Lager Image
Similarly we can show that
PPT Slide
Lager Image
Hence, d G1G2 ( u 1 , u 2 ) = d G2 ( u 2 ) + | V 2 | d G1 ( u 1 ). □
Example 3.6. Consider the vague graphs G 1 , G 2 and G 1 G 2 as follows.
Here, t A1 t B2 , f A1 f B2 , t A2 t B1 and f A2 f B1 . By Theorem 3.5, we have
PPT Slide
Lager Image
Therefore, d G1G2 ( u 1 , u 2 ) = (0.6, 2.1).
PPT Slide
Lager Image
So, d G1G2 ( u 1 , v 2 ) = (0.6, 2.1).
In the same way, we can find the degree of all the vertices in G 1 G 2 . This can be verified in the Figure 2 .
PPT Slide
Lager Image
Composition of G1 and G2
Degree of a vertex in the tensor product is as follows.
By definition of tensor product for any ( u 1 , u 2 ) ∈ V 1 × V 2 we have
PPT Slide
Lager Image
Theorem 3.7. Let G 1 = ( A 1 , B 1 ) and G 2 = ( A 2 , B 2 ) be two vague graphs. If t B2 t B1 and f B2 f B1 then d G1G2 ( u 1 , u 2 ) = d G1 ( u 1 ) . Also, if t B1 t B2 and f B1 f B2 then d G1⊗⊗G2 ( u 1 , u 2 ) = d G2 ( u 2 ).
Proof . Let t B2 t B1 , f B2 f B1 then we have
PPT Slide
Lager Image
Hence, d G1G2 ( u 1 , u 2 ) = d G1 ( u 1 ). Similarly if t B1 t B2 and f B1 f B2 , then d G1G2 ( u 1 , u 2 ) = d G2 ( u 2 ). □
Example 3.8. In this example we obtain the degree of vertices of G 1 G 2 by Theorem 3.7.
Consider the vague graphs G 1 and G 2 in Figure 3 . Here t B2 t B1 , f B2 f B1 . By Theorem 3.7 we have
PPT Slide
Lager Image
So, d G1G2 ( u 1 , u 2 ) = (0.2, 0.5) and d G1G2 ( v 1 , v 2 ) = (0.2, 0.5). Similarly, we can find the degree of all the vertices in G 1 G 2 . This can be verified in the Figure 3 .
PPT Slide
Lager Image
Tensor product of G1 and G2
Finally, we derive the degree of a vertex in normal product. By the definition of normal product for any ( u 1 , u 2 ) ∈ V 1 × V 2 we have
PPT Slide
Lager Image
Theorem 3.9. Let G 1 = ( A 1 , B 1 ) and G 2 = ( A 2 , B 2 ) be two vague graphs. If t A1 t B2 , f A1 f B2 , t A2 t B1 , f A2 f B1 , t B1 t B2 and f B1 f B2 then d G1G2 ( u 1 , u 2 ) = | V 2 | d G1 ( u 1 ) + d G2 ( u 2 ).
Proof .
PPT Slide
Lager Image
In the same way we can show that
PPT Slide
Lager Image
Hence, d G1G2 ( u 1 , u 2 ) = | V 2 | d G1 ( u 1 ) + d G2 ( u 2 ). □
Example 3.10. In this example we obtain the degree of vertices of G 1 G 2 by Theorem 3.9.
Consider the vague graphs G 1 and G 2 in Figure 4 . Here t A1 t B2 , f A1 f B2 , t A2 t B1 , f A2 f B1 , t B1 t B2 and f B1 f B2 . So, by Theorem 3.9 we have
PPT Slide
Lager Image
Therefore, d G1G2 ( u 1 , u 2 ) = (0.6, 2).
PPT Slide
Lager Image
So, d G1G2 ( u 1 , v 2 ) = (0.6, 2).
PPT Slide
Lager Image
Normal product of G1 and G2
Similarly, we can find the degree of all the vertices in G 1 G 2 . This can be verified in the Figure 4 .
4. Conclusion
Graph theory has several interesting applications in system analysis, operations research, computer applications, and economics. Since most of the time the aspects of graph problems are uncertain, it is nice to deal with these aspects via the methods of fuzzy systems. It is known that fuzzy graph theory has numerous applications in modern science and engineering, neural networks, expert systems, medical diagnosis, town planning and control theory. In this paper, we have found the degree of vertices in G 1 × G 2 , G 1 G 2 , G 1 G 2 and G 1 G 2 in terms of the degree of vertices in G 1 and G 2 under some conditions and illustrated them through examples. This will be helpful when the graphs are very large and it can help us in studying various properties of cartesian product, composition, tensor product and normal product of two vague graphs.
Acknowledgements
The authors are extremely grateful to the Editor in Chief Prof. Cheon Seoung Ryoo and anonymous referees for giving them many valuable comments and helpful suggestions which helps to improve the presentation of this paper.
BIO
R.A. Borzooei is Professor of Math., Shahid Beheshti University of Tehran, Tehran, Iran. His research interests include Fuzzy Graphs Theory, Fuzzy logical algebras, BL-algebras, BCK and BCI-algebras.
Department of Mathematics, Islamic Azad University, Central Tehran Branch, Tehran, Iran.
e-mail: borzooei@sbu.ac.ir
H. Rashmanlou
Department of Mathematics, Islamic Azad University, Central Tehran Branch, Tehran, Iran.
e-mail: Rashmanlou.1987@gmail.com
References
Abu Nayeem Sk. Md. , Pal M. (2008) The p-center problem on fuzzy networks and reduction of cost Iranian Journal of Fuzzy Systems 5 1 - 26
Akram M. , Gani N. , Borumand Saeid A. (2014) Vague hypergraphs Journal of Intelligent and Fuzzy Systems 26 647 - 653
Akram M. , Feng F. , Sarwar S. , Jun Y.B. (2014) Certain types of vague graphs University Politehnica of Bucharest Scientific Bulletin Series A 76 141 - 154
Akram M. , Murtaza Yousaf M. , Dudek Wieslaw A. 2014 Regularity in vague intersection graphs and vague line graphs Abstract and Applied Analysis Article ID 525389    DOI : 10.1155/2014/525389
Gau W.L. , Buehrer D.J. (1993) Vague sets IEEE Transactions on Systems, Man and Cybernetics 23 610 - 614    DOI : 10.1109/21.229476
Kauffman A. (1973) Introduction a la Theorie des Sous-Emsembles Flous,1 Masson et Cie
Mordeson J.N. , Nair P.S. 2000 Fuzzy Graphs and Fuzzy Hypergraphs Physica Verlag
Pal M. , Rashmanlou H. (2013) Irregular interval-valued fuzzy graphs Annals of Pure and Applied Mathematics 3 56 - 66
Ramakrishna N. (2009) Vague graphs International Journal of Computational Cognition 7 51 - 58
Rashmanlou H. , Pal M. (2013) Antipodal interval-valued fuzzy graphs International Journal of Applications of Fuzzy Sets and Artificial Intelligence 3 107 - 130
Rashmanlou H. , Pal M. (2013) Balanced interval-valued fuzzy graph Journal of Physical Sciences 17 43 - 57
Rashmanlou H. , Pal M. (2013) Some properties of highly irregular interval-valued fuzzy graphs World Applied Sciences Journal 27 1756 - 1773
Rashmanlou H. , Jun Y.B. (2013) Complete interval-valued fuzzy graphs Annals of Fuzzy Mathematics and Informatics 6 677 - 687
Rashmanlou H. , Samanta S. , Pal M. , Borzooei R.A. (2015) A study on bipolar fuzzy graphs Journal of Intelligent and Fuzzy Systems 28 571 - 580
Rosenfeld A. (1975) Fuzzy graphs in Fuzzy Sets and Their Applications, L. A. Zadeh, K. S. Fu, and M. Shimura, Eds. Academic Press New York, NY, USA 77 - 95
Samant S. , Pal M. (2011) Fuzzy tolerance graphs International Journal Latest Trend Mathematics 1 57 - 67
Samanta S. , Pal M. (2011) Fuzzy threshold graphs CiiT International Journal of Fuzzy Systems 3 360 - 364
Samanta S. , Pal M. , Pal A. (2014) New concepts of fuzzy planar graph International Journal of Advanced Research in Articial Intelligence 3 52 - 59
Samanta S. , Pal M. (2013) Fuzzy k-competition graphs and p-competition fuzzy graphs Fuzzy Engineering and Information 5 191 - 204    DOI : 10.1007/s12543-013-0140-6
Samanta S. , Pal M. (2012) Irregular bipolar fuzzy graphs International Journal of Application Fuzzy Sets 2 91 - 102    DOI : 10.4018/ijfsa.2012040105
Samanta S. , Pramanik T. , Pal M. Fuzzy colouring of fuzzy graphs Afrika Matematika    DOI : 10.1007/s13370-015-0317-8
Samanta S. , Pal M. (2012) Bipolar fuzzy hypergraphs International Journal of Fuzzy Logic Systems 2 17 - 28    DOI : 10.5121/ijfls.2012.2103
Samanta S. , Pal M. , Pal A. (2014) Some more results on fuzzy k-competition graphs International Journal of Advanced Research in Artificial Intelligence 3 60 - 67
Samanta S. , Pal M. (2014) Some more results on bipolar fuzzy sets and bipolar fuzzy inter-section graphs The Journal of Fuzzy Mathematics 22 253 - 262
Zadeh L.A. (1965) Fuzzy sets Information and Control 8 338 - 353    DOI : 10.1016/S0019-9958(65)90241-X
Zadeh L.A. (1971) Similarity relations and fuzzy ordering Information Sciences 3 177 - 200    DOI : 10.1016/S0020-0255(71)80005-1