Abstract
Fuzzy graph theory is commonly used in computer science applications, particularly in database theory, data mining, neural networks, expert systems, cluster analysis, control theory, and image capturing. 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 introduce the notion of vague line graphs, and certain types of vague line graphs and present some of their properties. We also discuss an example application of vague digraphs.
1. Introduction
During the last twenty years, line graphs have received considerable attention [1]. A line graph of a graph , the vertex set of is and two vertices in are adjacent if and only if their corresponding edges in are adjacent. Thus line graphs transform the adjacency relation on edges to an adjacency relation on vertices and thereby provide a mechanism for transferring problems and results on edges to analogous problems and findings about vertices. One of the major results on line graphs is Beineke’s [2] characterization of line graphs by a set of nine forbidden induced subgraphs. This approach of finding a forbidden induced subgraph characterization is a popular method of studying the structure of a graph family and has proven to be especially useful for line graphs of various families of graphs.
In 1993, Gau and Buehrer [3] introduced the notion of vague set theory as a generalization of Zadeh’s fuzzy set theory. Vague sets are higher order fuzzy sets. Application of higher order fuzzy sets makes the solution procedure more complex, but if the complexity on computation time, computation volume, or memory space is not a matter of concern, then we can achieve better results. In a fuzzy set, each element is associated with a point value selected from the unit interval , which is termed as the grade of membership in the set. Instead of using point-based membership as in fuzzy sets, interval-based membership is used in a vague set. The interval-based membership in vague sets is more expressive in capturing vagueness of data. There are some interesting features for handling vague data that are unique to vague sets. For example, vague sets allow for a more intuitive graphical representation of vague data, which facilitates significantly better analysis in data relationships, incompleteness, and similarity measures.
In 1975, Rosenfeld [4] first discussed the concept of fuzzy graphs whose basic idea was introduced by Kauffman [5] in 1973. Rosenfeld also proposed the fuzzy relations between fuzzy sets and developed the structure of fuzzy graphs, obtaining analogs of several graph theoretical concepts. Moreover, Bhattacharya [6] gave some remarks on fuzzy graphs and Mordeson [7] introduced the notion of fuzzy line graphs. Bhutani and Battou [8] introduced the concept of -strong fuzzy graphs and described some of their properties. Akram and Dudek [9] discussed some properties of the interval-valued fuzzy graphs. Ramakrishna [10] introduced the concept of vague graphs and studied some of their properties. In this paper, we introduce the notion of vague line graphs and present some of their properties. We introduce the concept of certain types of vague line graphs and present some of their properties. We also describe an example application of vague digraphs.
2. Preliminaries
By a graph, we mean a pair , where is the set and is a relation on . The elements of are vertices of and the elements of are edges of . We write to mean , and if , we say and are adjacent. Formally, given a graph , two vertices are said to be neighbors or adjacent nodes if . The neighbourhood of a vertex in a graph is the induced subgraph of consisting of all vertices adjacent to and all edges connecting two such vertices. The neighbourhood is often denoted by . The degree of vertex is the number of edges incident on . The set of neighbors, called an open neighborhood for a vertex in a graph , consists of all vertices adjacent to but not including ; that is, . When is also included, it is called a closed neighborhood ; that is, . A regular graph is a graph where each vertex has the same number of neighbors; that is, all the vertices have the same closed neighbourhood degree. An undirected graph is connected if there is a path between each pair of distinct vertices. A connected graph is an irregular graph if each of its vertices is adjacent only to vertices with distinct degrees.
An isomorphism of graphs and is a bijection between the vertex sets of and such that any two vertices and of are adjacent in if and only if and are adjacent in . Isomorphic graphs are denoted by .
By an intersection graph of a graph , we mean a pair , where is a family of distinct nonempty subsets of and . It is well known that every graph is an intersection graph. By a line graph of a graph , we mean a pair , where and , and , . It is reported in the literature that the line graph is an intersection graph.
Proposition 1. If is regular of degree , then the line graph is regular of degree .
Definition 2 (see [11, 12]). A fuzzy subset on a set is a map . A fuzzy binary relation on is a fuzzy subset on . By a fuzzy relation one means a fuzzy binary relation given by .
Definition 3 (see [3]). A vague set in the universe of discourse is a pair , where , are true and false membership functions, respectively, such that for all .
In the above definition, is considered as the lower bound for degree of membership of in (based on evidence for), and is the lower bound for negation of membership of in (based on evidence against). Therefore, the degree of membership of in the vague set is characterized by the interval . So, a vague set is a special case of interval-valued sets studied by many mathematicians and applied in many branches of mathematics (see, e.g., [9, 13, 14]). Vague sets also have many applications (cf. [15–17]). The interval is called the vague value of in and is denoted by . We denote zero vague and unit vague value by and , respectively.
It is worth mentioning here that interval-valued fuzzy sets are not vague sets. In interval-valued fuzzy sets, an interval-valued membership value is assigned to each element of the universe considering the “evidence for ” only, without considering “evidence against .” In vague sets both are independently proposed by the decision maker. This makes a major difference in the judgment about the grade of membership.
A vague relation is a further generalization of a fuzzy relation.
Definition 4. Let and be ordinary finite nonempty sets. One can call a vague relation a vague subset of , that is, an expression defined by where and , which satisfies the condition , for all .
3. Vague Intersection Graphs and Vague Line Graphs
Throughout this paper, will be a crisp graph and a vague graph (see Figures 2 and 4). Since an edge is identified with an ordered pair , a vague relation on can be identified with a vague set on . This gives a possibility to define a vague graph as a pair of vague sets.
Definition 5 (see [10]). A vague relation on a set is a vague relation from to . If is a vague set on a set , then a vague relation on is a vague relation which satisfies for all , .
Definition 6 (see [10]). Let be a nonempty set; members of are called nodes. A vague graph with as the set of nodes is a pair of functions and , where is a vague set of and is a vague relation on .
We note that vague relation in vague digraph need not be symmetric.
Example 7. Consider a graph such that and . Let be a vague set on , and let be a vague relation on defined by Table 1.
By routine computations, it is easy to see from Figure 1 that is a vague digraph.
Definition 8. Consider an intersection graph of a crisp graph . Let and be vague sets on and and and on and , respectively. Then a vague intersection graph of the vague graph is a vague graph such that (a), ,(b),
for all , .
Example 9. Consider a graph , where is the set of vertices and is the set of edges. Consider , where and are vague set and vague relation on , respectively. We define Table 2.
By routine computations, it is easy to see from Figure 3 that is a vague graph. Consider an intersection graph such that
Let and be vague sets on and , respectively. Then, by routine computations, we have
By routine computations, it is easy to see that is a vague intersection graph.
Proposition 10. Let be a vague graph of and let be a vague intersection graph of . Then (a) a vague intersection graph is a vague graph; (b) a vague graph is isomorphic to a vague intersection graph.
Proof. (a) From Definition 6, it follows that
This shows that a vague intersection graph is a vague graph.
(b) Define by , for . Clearly, is a one-to-one function of onto . Now if and only if and . Also
Thus is an isomorphism of onto .
Definition 11. Let be a line graph of a crisp graph . Let and be vague sets on and and and on and , respectively. Then a vague line graph of the vague graph is a vague graph such that (i),(ii),(iii),(iv)
for all .
Example 12. Consider a crisp graph , where is the set of vertices, and is the set of edges. Let be a vague set on and let be vague relation on defined by Table 3.
By routine computations, it is easy to see that is a vague graph. Consider a line graph such that
Let and be vague sets on and , respectively. Then, by routine computations, we have
By routine computations, it is clear that is a vague line graph (see Figure 5).
Remark 13. is a vague line graph corresponding to the vague graph .
Proposition 14. If is a vague line graph of a vague graph , then is the line graph of .
Proposition 15. is a vague line graph of some vague graph if and only if for all .
Proof. Assume that for all , . We define for all . Then
A vague set that yields the properties
will suffice.
The converse part is obvious.
Another characterization of vague line graphs of vague graphs is given by the following proposition.
Proposition 16. is a vague line graph of some vague graph if and only if is a line graph such that for all .
Definition 17. Let and be two vague graphs. A homomorphism is a mapping such that (a), ,(b),
for all , , and .
A bijective homomorphism of vague graphs is called a weak vertex-isomorphism if (c), ,
for all , and a weak line-isomorphism if (d), ,
for all . A bijective homomorphism satisfying and is called a weak isomorphism of vague graphs and . A weak isomorphism preserves the weights of the vertices but not necessarily the weights of the edges.
The following fact is obvious.
Proposition 18. A weak isomorphism of vague graphs and is an isomorphism of their crisp graphs and .
Theorem 19. Let be the vague line graph corresponding to the vague graph . Suppose that is connected. Then one has the following. (i)There exists a weak isomorphism of onto if and only if is a cycle and for all , , , ; that is, and are constant functions on and , respectively, taking on the same value. (ii)If is a weak isomorphism of onto , then is an isomorphism.
Proof. Assume that is a weak isomorphism of onto . From Proposition 15, it follows that is a cycle [18, Theorem 8.2, page 72]. Let and , where is a cycle. Define vague sets
Then for and , we have
Now
Thus for , we obtain
for , . Since is an isomorphism of onto , is a bijective map of onto . Also preserves adjacency. Hence induces a permutation of such that
Thus
Similarly,
for . That is,
Thus, and and so and for all . Continuing, we obtain
where is the identity map. So, and for all . But, by (21), we also have and , which together with and imply and for all . Hence by (14) and (20), we get
Thus we have not only proven the conclusion about and being constant function, but also shown that (ii) holds.
The converse part of (i) is obvious.
We state the following theorem without proof.
Theorem 20. Let and be vague graphs of and , respectively, such that and are connected. Let and be the line graphs corresponding to and , respectively. Suppose that it is not the case that one of and is complete graph and the other is bipartite complete graph . If and are isomorphic, then and are line-isomorphic.
4. Regular Vague Intersection Graphs and Vague Line Graphs
Definition 21. A vague graph is called complete if for each edge .
Example 22. Consider a vague graph .
Routine computations show that is complete (see Figure 6).
Definition 23. Let be a vague graph on . If all the vertices have the same open neighbourhood degree , then is called a regular vague graph. The neighbourhood degree of a vertex in is defined by , where and .
Definition 24. Let be a vague graph. The closed neighbourhood degree of a vertex is defined by , where If each vertex of has the same closed neighbourhood degree , then is called a totally regular vague graph.
Example 25. Consider a graph such that and . Let be a vague subset of and let be a vague subset of defined by
Routine computations show that a vague graph is both regular and totally regular.
Definition 26. If there is a vertex which is adjacent to vertices with distinct open neighbourhood degrees, then is called an irregular vague graph (see Figure 8). That is, for all . If there is a vertex which is adjacent to vertices with distinct closed neighbourhood degrees, then is called a totally irregular vague graph (see Figure 9).
Example 27. Consider a graph such that Let be a vague subset of and let be a vague subset of defined by Table 4.
By routine computations, we have , , and . It is clear that is an irregular vague graph.
Example 28. Consider a graph such that and . Let be a vague subset of and let be a vague subset of defined by Table 5.
Routine computations show that a vague graph is both irregular and totally irregular.
Remark 29. In classical (crisp) graph theory, any complete graph is regular, but a complete vague graph is not regular, in general (see Figure 10).
Example 30. Consider a graph such that and . Let be a vague subset of and let be a vague subset of defined by
Clearly, is a complete vague graph, but is not regular since .
Definition 31 (see [10]). The complement of a vague graph of is a vague graph on , where and are defined by (i)(ii)(iii)
Definition 32. A vague graph is called self-complementary if .
Example 33. Consider a vague graph . (1)Clearly, graph is not isomorphic to its complement . Hence is not self-complementary.(2)Routine calculations show that and are irregular and totally irregular, respectively (see Figures 11 and 12).
Example 34. Consider a vague graph . (1)Clearly, is isomorphic to its complement . Hence is self-complementary.(2)Routine calculations show that and are irregular and totally irregular, respectively.
Theorem 35. Let be a vague graph of a graph . Then is a constant function if and only if the following are equivalent: (a) is a regular vague graph,(b) is a totally regular vague graph.
Proof. Let be a constant function. To prove that and are equivalent, suppose that and for all .
: If a vague graph is -regular, then and for all . So
Thus
Hence, is totally regular.
: Suppose that is totally regular. Then for all , we have
Hence,
Similarly we obtain for every , where . This means that is regular (see Figure 7).
Hence and are equivalent.
The converse part is obvious.
Example 36. Consider a graph such that and . Let and be vague subsets defined by Clearly, is constant and is both regular and totally regular.
Finally, we consider examples of vague intersection graph and vague line graph.
Example 37. Consider vague intersection graph which is given in Example 9. Routine calculations show that is an irregular vague intersection graph, but it is totally regular vague intersection graph.
Example 38. Consider vague line graph which is given in Example 12. Routine calculations show that is both irregular and totally irregular vague line graph.
5. Application Example of Vague Digraphs
Graph models find wide application in many areas of mathematics, computer science, and the natural and social sciences. Often these models need to incorporate more structure than simply the adjacencies between vertices. In studies of group behavior, it is observed that certain people can influence thinking of others. A directed graph, called an influence graph, can be used to model this behavior. Each person of a group is represented by a vertex. There is a directed edge from vertex to vertex , when the person represented by vertex influences the person represented by vertex . This graph does not contain loops and it does not contain multiple directed edges.
We now explore vague influence graph model to find out the influential person within a social group. In influence graph, the vertex (node) represents a power (authority) of a person and the edge represents the influence of a person on another person in the social group.
Consider a vague influence graph of a social group. In Figure 13, vague influence graph, the degree of power of a person is defined in terms of its trueness and falseness. The node of the vague influence graph shows the authority a person possesses in the group; for example, Tanzel has 60% authority in the group, but he does not have 20% power, and 20% power is not decided, whereas the edges show the influence of a person on another in a group; for example, Tanzel can influence Amir 30%, but he cannot convince him 60%, and remaining 10% is hesitation part.
The degree of a vertex and edge in a vague influence graph is also characterized by an interval . It is worth mentioning here that interval-valued fuzzy sets are not vague sets. In interval-valued fuzzy sets, an interval-valued membership value is assigned to each element of the universe considering the “evidence for ” only, without considering “evidence against .” In vague sets both are independently proposed by the decision maker. Thus the vague influence graph can be interpreted in the form of interval-valued membership. The node of the vague influence graph shows the likelihood of power a person possesses in the group; for example, Tanzel posseses to power, whereas the edges show the interval of influence a person has on another person in a social group. Tanzel has to influence on Amir and Amir has to influence on Rajab.
6. Conclusions
In 1965, Zadeh introduced the concept of fuzzy sets by extending the range of Eigenfunction of classical sets from to a closed interval . However, the membership function of a fuzzy set is a single-valued function, which cannot express either the evidence for or the evidence against . For overcoming the shortcoming, Gau and Buehrer proposed the concept of a vague set in 1993, which is a generalization of the fuzzy set. Essentially, in a fuzzy set each element is associated with a point-value selected from the unit interval , which is termed the grade of membership in the set. Instead of using point-based membership as in fuzzy sets, interval-based membership is used in a vague set. The interval-based membership in vague sets is more expressive in capturing vagueness of data. We investigate the concepts of vague line and develop the vague influence graph of a social group. The natural extension of this work is exploration of the applications of vague graphs in database theory, expert systems, and neural networks.
Conflict of Interests
The authors declare that they do not have any conflict of interests regarding the publication of this paper.