EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 10, No. 3, 2017, 552-560 ISSN 1307-5543 – www.ejpam.com Published by New York Business Global Certain Classes of fuzzy graphs Talal Al-Hawary Department of Mathematics, Faculty of Sciences, Yarmouk University, Jordan Abstract. In this paper, several classes of fuzzy graphs are characterized and we provide two new operations on fuzzy graphs; namely parallel connection and series connection. We show that parallel connection and series connection of balanced fuzzy graphs need not be balanced and they are balanced in case the original graphs are induced by cycles. Finally, we study the notions of strong and complete via these operations. 2010 Mathematics Subject Classifications: 05C72 1. Introduction A graph is a nice way of representing information involving relationships between objects where objects are represented by vertices and relations by edges. When there is vagueness in the description of the objects or relationships, it is natural that we think of it as what is called ’Fuzzy Graph Model’. Applications of fuzzy relations are widespread and important in many fields; especially in the field of clustering analysis, neural networks, computer networks, pattern recognition, decision making and expert systems. In each of these, the basic mathematical structure is that of a fuzzy graph. The notion of fuzzy relation was introduced by Zadeh [17] in his landmark paper ”Fuzzy sets” in 1965. Fuzzy graph and several fuzzy analogs of graph theoretic concepts were introduced by Rosenfeld [15] in 1975. After that, the theory of fuzzy graph started to finding an increasing number of applications in several fields. Mordeson and Peng [9] defined the concept of fuzzy graph complement and introduced several operations on fuzzy graphs. In [16], the definition of complement of a fuzzy graph was modified to agree with the classical graph case. Moreover, some properties of self- complementary fuzzy graphs and complements of several operations of fuzzy graphs that were introduced in [9] were discussed. Al-Hawary [1] introduced and explored the new notion of balanced fuzzy graphs and several new operations. After that, balanced concept was studied by many authors. The idea of balanced came from matroids, see [2, 3, 4, 6]. Email addresses: talalhawary@yahoo.com (T. A. Hawary) This work has been done during the author’s sabbatical leave at Jordan University of Science and Technology---Jordan. http://www.ejpam.com 552 c© 2017 EJPAM All rights reserved. T. A. Hawary / Eur. J. Pure Appl. Math, 10 (3) (2017), 552-560 553 For a complete background on the previous notions and the following ones, the reader is referred to [1, 5, 7, 9, 10, 11, 12, 13, 14, 15, 16]. A fuzzy subset of a non-empty set V is a mapping σ : V → [0, 1] and a fuzzy relation µ on a fuzzy subset σ, is a fuzzy subset of V × V. All throughout this paper, we assume that σ is reflexive, µ is symmetric and V is finite. Definition 1. [15] A fuzzy graph with V as the underlying set is a pair G : (σ, µ) where σ : V → [0, 1] is a fuzzy subset and µ : V × V → [0, 1] is a fuzzy relation on σ such that µ(x, y) ≤ σ(x)∧ σ(y) for all x, y ∈ V, where ∧ stands for minimum. The underlying crisp graph of G is denoted by G∗ : (σ∗, µ∗) where σ∗ = sup p(σ) = {x ∈ V : σ(x) > 0} and µ∗ = sup p(µ) = {(x, y) ∈ V × V : µ(x, y) > 0}.H = (σ′, µ′) is a fuzzy subgraph of G if there exists X ⊆ V such that, σ′ : X → [0, 1] is a fuzzy subset and µ′ : X ×X → [0, 1] is a fuzzy relation on σ′ such that µ(x, y) ≤ σ(x) ∧ σ(y) for all x, y ∈ X. Definition 2. [14] A fuzzy graph G : (σ, µ) with underlying graph G : (V,E) is complete if µ(x, y) = σ(x) ∧ σ(y) for all x, y ∈ V. Definition 3. [14] A fuzzy graph G : (σ, µ) with underlying graph G : (V,E) is strong if µ(x, y) = σ(x) ∧ σ(y) for all {x, y} ∈ E. Definition 4. [8] Two fuzzy graphs G1 : (σ1, µ1) with crisp graph G∗1 : (V1, E1) and G2 : (σ2, µ2) with crisp graph G∗2 : (V2, E2) are isomorphic if there exists a bijection h : V1 → V2 such that σ1(x) = σ2(h(x)) and µ1(x, y) = µ2(h(x), h(y)) for all x, y ∈ V1. Next, we recall the following definition of balanced fuzzy graphs that will be our main concern in this paper. It was motivated and deeply studied by Al-Hawary in [1, 5, 7]. Definition 5. [1] The density of a fuzzy graph G : (σ, µ) is D(G) = 2( ∑ u,v∈V µ(u, v))/( ∑ u,v∈V u6=v (σ(u) ∧ σ(v))). G is balanced if. D(H) ≤ D(G) for all fuzzy non-empty subgraphs H of G. In this paper, several classes of balanced fuzzy graphs are characterized; namely the classes of complete fuzzy graphs, fuzzy graphs induced by the complete graph, fuzzy graphs with balanced components, fuzzy graphs induced by trees and fuzzy graphs induced by cycles. Moreover, we provide two new operations on fuzzy graphs, namely parallel connection and series connection. We show that parallel connection and series connection of balanced fuzzy graphs need not be balanced and they are balanced in case the original graphs are induced by cycles. Finally, we study the notions of strong and complete via these operations. T. A. Hawary / Eur. J. Pure Appl. Math, 10 (3) (2017), 552-560 554 2. Classes of balanced fuzzy graphs In this section, several classes of balanced fuzzy graphs are provided. The first class of balanced fuzzy graphs is the class of complete fuzzy graphs. Theorem 1. [1] Any complete fuzzy graph is balanced. By a fuzzy graph G : (σ, µ) induced by a graph G : (V,E), we mean the the graph G after assigning values σ(x) for all x ∈ V and µ(x, y) for all {x, y} ∈ E where each σ(x) and µ(x, y) are in the interval [0, 1]. Theorem 2. A fuzzy graph G induced by the complete graph Kn is balanced. Proof. Let H be a fuzzy subgraph of G with m vertices. We claim that the many possible cases of H reduce to the case that H is is induced by a complete graph Km. If this is true, then as ∑ x,y∈V (Km) µ(x, y) ≤ ∑ x,y∈V (Kn) µ(x, y) and ∑ x,y∈V (Kn) (σ ′ 2(x)∧σ′ 2(y)) ≤∑ x,y∈V (Km)(σ ′ 2(x) ∧ σ′ 2(y)), we have D(H) = 2 ∑ x,y∈V (Km) µ(x, y)∑ x,y∈V (Km)(σ ′ 2(x) ∧ σ′ 2(y)) ≤ 2 ∑ x,y∈V (Kn) µ(x, y)∑ x,y∈V (Kn) (σ ′ 2(x) ∧ σ′ 2(y)) = D(G). Therefore, G is balanced. To show the claim is true, let H′ be a fuzzy subgraph of with k vertices. Obviously, D(H′) ≤ D(H) since the corresponding graphs of both have same vertices and that of H has more edges. Lemma 3. The union of two balanced fuzzy graphs is balanced. Proof. If G1 : (σ1, µ1) is a fuzzy balanced graph with crisp graph G∗1 : (V1, E1) and G2 : (σ2, µ2) is a fuzzy balanced graph with crisp graph G∗2 : (V2, E2),where we assume that V1 ∩ V2 = ∅, then for any fuzzy subgraph H of G1 ∪G2, H ' H1 ∪H2 for some fuzzy subgraphs H1 of G1 and H2 of G2. Now ∑ x,y∈V (H1)∪V (H2) µ(x, y) ≤ ∑ x,y∈V1∪V2 µ(x, y) and ∑ x,y∈V1∪V2 (σ ′ 2(x) ∧ σ′ 2(y)) ≤ ∑ x,y∈V (H1)∪V (H2)) (σ ′ 2(x) ∧ σ′ 2(y)) and so D(H) = 2 ∑ x,y∈V (H1)∪V (H2) µ(x, y)∑ x,y∈V (H1)∪V (H2)) (σ ′ 2(x) ∧ σ′ 2(y)) ≤ 2 ∑ x,y∈V1∪V2 µ(x, y)∑ x,y∈V1∪V2 (σ ′ 2(x) ∧ σ′ 2(y)) = D(G1 ∪G2). Therefore, G1 ∪G2 is balanced. Although the union of two balanced fuzzy graphs is balanced, the intersection (join) of two balanced fuzzy graphs needs not be balanced. Example 1. Consider the fuzzy graphs G1 : (σ1, µ1) with crisp graph G∗1 : (V1, E1) where V1 = {v1, v2}, σ1(v1) = 1/2, σ1(v2) = 1/3 and µ1(v1, v2) = 1/3 and G2 : (σ2, µ2) with crisp graph G∗2 : (V2, E2) where V2 = {w1, w2}, σ2(w1) = 1, σ2(w2) = 1 and µ2(w1, w2) = 1. Then G1 and G2 are balanced, while the intersection (join) of G1 and G2 is not balanced as the join has density equals to 71/90 while the fuzzy subgraph G1 of the join has density equals to 2. T. A. Hawary / Eur. J. Pure Appl. Math, 10 (3) (2017), 552-560 555 The following result can be proved by induction on the number of components of a fuzzy graph G. Corollary 1. If G : (σ, µ) is a fuzzy graph with each of its component is balanced, then G is balanced. Theorem 4. A fuzzy graph G induced by a tree with n vertices is balanced. Proof. Let H be a fuzzy subgraph of G with m vertices. Since all subgraphs of trees are forests, we have the following two case: Case 1: H is induced by a tree Tm. Then as ∑ x,y∈V (Tm) µ(x, y) ≤ ∑ x,y∈V (Tn) µ(x, y) and ∑ x,y∈V (Tn) (σ ′ 2(x) ∧ σ′ 2(y)) ≤ ∑ x,y∈V (Tm)(σ ′ 2(x) ∧ σ′ 2(y)), we have D(H) = 2 ∑ x,y∈V (Tm) µ(x, y)∑ x,y∈V (Tm)(σ ′ 2(x) ∧ σ′ 2(y)) ≤ 2 ∑ x,y∈V (Tn) µ(x, y)∑ x,y∈V (Tn) (σ ′ 2(x) ∧ σ′ 2(y)) = D(G). Case 2: H is induced by a forest K with m vertices and p ≥ 2 components. Let the number of vertices in each tree be ni for i = 1, 2, ..., p. Since a forest is a disjoint union of trees, by Lemma 3, G is balanced. Corollary 2. A fuzzy graph G induced by a forest is balanced. Theorem 5. A fuzzy graph G induced by the cycle Cn is balanced. Proof. Let H be a proper fuzzy subgraph of G . It is easy to see that H is induced by forests. Now by Corollary 2, forests are balanced and by Lemma 3, G is balanced as a a union of balanced fuzzy graphs. 3. Series and parallel connections The operations of joining electrical components in parallel and in series are very impor- tant in electrical network theory. Graphs may be also constructed through an operation known as the parallel connection. This can be defined as adding elements in parallel to some existing element. That is as doubling one or more elements. It is also can be constructed through an operation known as the series connection. Analogously, in this section, we introduce two new operations on fuzzy graphs; namely series and parallel con- nections. To describe these operations, let G1 : (σ1, µ1) be a fuzzy graph with crisp graph G∗1 : (V1, E1) and G2 : (σ2, µ2) be a fuzzy graph with crisp graph G∗2 : (V2, E2) and let e1 = {v1, v′1} ∈ E1 and e2 = {v2, v′2} ∈ E2. For i = 1, 2, arbitrary assign a direction to ei and say its tail vi and its head v′i . Definition 6. Let G1 : (σ1, µ1) be a fuzzy graph with crisp graph G∗1 : (V1, E1) and G2 : (σ2, µ2) be a fuzzy graph with crisp graph G∗2 : (V2, E2). The parallel connection of G1 and G2 with respect to the directed edges e1 and e2 is the fuzzy graph P ((G1, e1); (G2, e2)) T. A. Hawary / Eur. J. Pure Appl. Math, 10 (3) (2017), 552-560 556 obtained by deleting the edge e1 from G1 and the edge e2 from G2 and then identify the vertices v1, v2 as the vertex v with σ(v) = σ1(v1) ∧ σ2(v2) and v′1, v′2 as the vertex v′ with σ(v′) = σ1(v ′ 1) ∧ σ2(v′2) and finally adding a new edge e joining v and v′ with µ(v, v′) = µ1(v1, v ′ 1) ∧ µ2(v2, v′2). Definition 7. Let G1 : (σ1, µ1) be a fuzzy graph with crisp graph G∗1 : (V1, E1) and G2 : (σ2, µ2) be a fuzzy graph with crisp graph G∗2 : (V2, E2). The series connection of G1 and G2 with respect to the directed edges e1 and e2 is the fuzzy graph S((G1, e1); (G2, e2)) obtained by deleting the edge e1 from G1 and the edge e2 from G2 and then identify the vertices v1, v2 as the vertex v with σ(v) = σ1(v1) ∧ σ2(v2) and finally adding a new edge e joining v′1, v′2 with µ(v′1, v ′ 2) = µ1(v1, v ′ 1) ∧ µ2(v2, v′2). The connecting edges in P ((G1, e1); (G2, e2)) and S((G1, e1); (G2, e2)) are usually ar- bitrary and so we instead write P (G1;G2) and S(G1;G2), respectively. To illustrate these definitions, we offer the following example: Example 2. Consider the fuzzy graphs G1, G2, P (G1;G2) and S(G1;G2) in Figure 1. T. A. Hawary / Eur. J. Pure Appl. Math, 10 (3) (2017), 552-560 557 As an application, we provide the following result which is immediate on the operation of union that was defined in [16]: Theorem 6. Let G1 : (σ1, µ1) be a fuzzy graph with crisp graph G∗1 : (V1, E1) and G2 : (σ2, µ2) be a fuzzy graph with crisp graph G∗2 : (V2, E2). Then a) If E1 ∩ E2 = ∅, then G1 ∪G2 = G1 ⊕G2. b) If E1 ∩ E2 = {e}, then G1 ∪G2 = S(G1;G2). In general, the series connection of two fuzzy graphs needs not be balanced. Example 3. Consider the fuzzy graphs G1, G2 and S(G1;G2) in Figure 2. The first graph with one edge removed is subgraph of S(G1;G2) that has density 1 which is greater than10 12 = D(S(G1;G2)).Thus S(G1;G2) is not balanced. We remark that in the preceding example, G1 and G2 are balanced. Thus the series connection of two balanced fuzzy graphs needs not be balanced. Theorem 7. The series connection of a fuzzy graph G1 : (σ1, µ1) induced by Cn and a fuzzy graph G2 : (σ2, µ2) induced by Cm is balanced. T. A. Hawary / Eur. J. Pure Appl. Math, 10 (3) (2017), 552-560 558 Proof. From the definition of series connection of two fuzzy graphs, it is obvious that S(G1;G2) is isomorphic to a fuzzy graph induced by the cycle Cn+m−1. Hence by Theorem 5, S(G1;G2) is balanced. We remark that the above result needs not be true in the case of parallel connection. Example 4. Consider the fuzzy graphs G1, G2 and P (G1;G2) in Figure 3. Now G1 is a subgraph of P (G1;G2) and D(G1) = 2 > .8 = D(P (G1;G2)). Thus P (G1;G2) is not balanced. Note that in the preceding example, G1 and G2 are complete and balanced while S(G1;G2) is not complete and not balanced. Theorem 8. Let G1 : (σ1, µ1) be a strong fuzzy graph with crisp graph G∗1 : (V1, E1) and G2 : (σ2, µ2) be a strong fuzzy graph with crisp graph G∗2 : (V2, E2).Then P (G1;G2) and S(G1;G2) are strong. Proof. We only prove the case of parallel connection. The case of series connection is similar. REFERENCES 559 Any edge {x, y} in P (G1;G2) is either an edge from G1 or an edge from G2 or it is the new edge. In the first two cases, the result is obvious. In the third case, µ(x, y) = µ1(x1, x2) ∧ µ2(y1, y2) for some {x1, x2} ∈ E1 and {y1, y2} ∈ E2. Thus µ(x, y) = σ1(x1) ∧ σ1(x2) ∧ σ2(y1) ∧ σ2(y2). As x1 and x2 are identified by x and y1 and y2 are identified by y and by definition of P (G1;G2), µ(x, y) = σ(x) ∧σ(y). Therefore, P (G1;G2) is strong. We end this section with the following immediate result: Corollary 3. Let G1 and G2 be complete fuzzy graphs. Then P (G1;G2) and S(G1;G2) are complete. Acknowledgement The author would like to thank the referee for useful comments and suggestions. References [1] T. AL-Hawary, Complete fuzzy graphs, International J. Math Comb. 4(2011), 26-34. [2] T. AL-Hawary, Fuzzy Closure Matroids, MATEMATIKA 32(1)(2016), 69-74. [3] T.Al-Hawary, Fuzzy flats, Indian J. Mathematics 55(2)(2013), 223-236. [4] T.Al-Hawary, On Balanced Graphs and Balanced Matroids, Math.Sci.Res.Hot- Line,4(7)(2000), pp. 35-45. [5] T. Al-Hawary and Bayan Horani, On intuitionistic product fuzzy graphs,to appear in Ital. J. Pure. & appl. Math. [6] T.Al-Hawary, On K-Balanced Matroids, Mu’tah Lil-Buhuth Wad- Dirasat,16(1),2001,pp. 15-23. [7] T. Al-Hawary and Bayan Horani, On product fuzzy graphs, Annals of fuzzy mathe- matics and Informatics 12(2)(2016), 279-294. [8] K. R. Bhutani, On automorphism of fuzzy graphs, Pattern Recognition Letter 9(1989), 159–162. [9] J. N. Mordeson and C. S. Peng, Operations on fuzzy graphs, Information Sciences 79(1994), 381-384. [10] M. Akram, Bipolar fuzzy graphs, Information Sciences 181 (24), 5548-5564. [11] M. Akram and W.A. Dudek, Interval-valued fuzzy graphs, Computers and Mathemat- ics with Applications 61 (2), 289-299. [12] A.Nagoor Gani and J. Malarvizhi, Isomorphism on fuzzy graphs, Int. J. Comp. and Math. Sci. 2(4)(2008), 190-196. REFERENCES 560 [13] A.Nagoor Gani and J. Malarvizhi, Isomorphism properties on strong fuzzy graphs, Int. J. Algorithms, Comp. and Math. 2 (1)(2009), 39-47. [14] A.Nagoor Gani and K. Radha, On regular fuzzy graphs, J. Physical Sciences 12(2008), 33-40. [15] A. Rosenfeld, Fuzzy graphs, in L.A. Zadeh, K.S. Fu, K. Tanaka and M. Shirmura (Eds.), Fuzzy and their applications to cognitive and decision processes, Academic Press, New York, 1975, 77-95. [16] M.S. Sunitha and A. V. Kumar, Complements of fuzzy graphs, Indian J. Pure Appl. Math. 33(9)(2002), 1451-1464. [17] L.A. Zadeh, Fuzzy sets, Inform. Control. 8(1965), 338-353.