# Regularity in Vague Intersection Graphs and Vague Line Graphs

Authors: Muhammad Akram; Wieslaw A. Dudek; M. Murtaza Yousaf
Journal: Abstract and Applied Analysis
 (2014)

---

## 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.


---

## Body

## 1. Introduction

During the last twenty years, line graphs have received considerable attention [1]. A line graph L
(
G
*
) of a graph G
*
=
(
V
,
E
), the vertex set of L
(
G
*
) is E and two vertices in L
(
G
*
) are adjacent if and only if their corresponding edges in G
* 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 [
0,1
], 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 M-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 agraph, we mean a pair G
*
=
(
V
,
E
), where V is the set and E is a relation on V. The elements of V are vertices of G
* and the elements of E are edges of G
*. We write x
y
∈
E to mean {
x
,
y
}
∈
E, and if e
=
x
y
∈
E, we say x and y areadjacent. Formally, given a graph G
*
=
(
V
,
E
), two vertices x
,
y
∈
V are said to beneighbors or adjacent nodes if x
y
∈
E. Theneighbourhood of a vertex v in a graph G
* is the induced subgraph of G
* consisting of all vertices adjacent to v and all edges connecting two such vertices. The neighbourhood is often denoted by N
(
v
). The degree of vertex v
deg
⁡
(
v
) is the number of edges incident on v. The set of neighbors, called anopen neighborhood
N
(
v
) for a vertex v in a graph G
*, consists of all vertices adjacent to v but not including v; that is, N
(
v
)
=
{
u
∈
V
∣
v
u
∈
E
}. When v is also included, it is called aclosed neighborhood
N
[
v
]; that is, N
[
v
]
=
N
(
v
)
∪
{
v
}. Aregular 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 G
* isconnected if there is a path between each pair of distinct vertices. A connected graph is anirregular graph if each of its vertices is adjacent only to vertices with distinct degrees.Anisomorphism of graphs G
1
* and G
2
* is a bijection between the vertex sets of G
1
* and G
2
* such that any two vertices v
1 and v
2 of G
1
* are adjacent in G
1
* if and only if f
(
v
1
) and f
(
v
2
) are adjacent in G
2
*. Isomorphic graphs are denoted by G
1
*
≃
G
2
*.By anintersection graph of a graph G
*
=
(
V
,
E
), we mean a pair P
(
S
)
=
(
S
,
T
), where S
=
{
S
1
,
S
2
,
…
,
S
n
} is a family of distinct nonempty subsets of V and T
=
{
S
i
S
j
∣
S
i
,
S
j
∈
S
,
S
i
∩
S
j
≠
∅
,
i
≠
j
}. It is well known that every graph is an intersection graph. By aline graph of a graph G
*
=
(
V
,
E
), we mean a pair L
(
G
*
)
=
(
Z
,
W
), where Z
=
{
{
x
}
∪
{
u
x
,
v
x
}
∣
x
∈
E
,
u
x
,
v
x
∈
V
,
x
=
u
x
v
x
} and W
=
{
S
x
S
y
∣
S
x
∩
S
y
≠
∅
,
x, y
∈
E
,
x
≠
y
} and S
x
=
{
x
}
∪
{
u
x
,
v
x
}, x
∈
E. It is reported in the literature that the line graph is an intersection graph.Proposition 1.
IfG
* is regular of degree k, then the line graph L
(
G
*
) is regular of degree 2
k
-
2.Definition 2 (see [11, 12]).
Afuzzy subset
μ on a set X is a map μ
:
X
→
[
0,1
]. Afuzzy binary relation on X is a fuzzy subset μ on X
×
X. By a fuzzy relation one means a fuzzy binary relation given by μ
:
X
×
X
→
[
0,1
].Definition 3 (see [3]).
Avague set
A in the universe of discourse X is a pair (
t
A
,
f
A
), where t
A
:
X
→
[
0,1
], f
A
:
X
→
[
0,1
] are true and false membership functions, respectively, such that t
A
(
x
)
+
f
A
(
x
)
≤
1 for all x
∈
X.In the above definition,t
A
(
x
) is considered as the lower bound for degree of membership of x in A (based on evidence for), and f
A
(
x
) is the lower bound for negation of membership of x in A (based on evidence against). Therefore, the degree of membership of x in the vague set A is characterized by the interval [
t
A
(
x
)
,
1
-
f
A
(
x
)
]. 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 [
t
A
(
x
)
,
1
-
f
A
(
x
)
] is called thevague value of x in A and is denoted by V
A
(
x
). We denote zero vague and unit vague value by 0
=
[
0,0
] and 1
=
[
1,1
], 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 forx” only, without considering “evidence against x.” 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.
LetX and Y be ordinary finite nonempty sets. One can call avague relation a vague subset of X
×
Y, that is, an expression R defined by
(1)
R
=
{
〈
(
x
,
y
)
,
t
R
(
x
,
y
)
,
f
R
(
x
,
y
)
〉
∣
x
∈
X
,
y
∈
Y
}
,
where t
R
:
X
×
Y
→
[
0,1
] and f
R
:
X
×
Y
→
[
0,1
], which satisfies the condition 0
≤
t
R
(
x
,
y
)
+
f
R
(
x
,
y
)
≤
1, for all (
x
,
y
)
∈
X
×
Y.


## 3. Vague Intersection Graphs and Vague Line Graphs

Throughout this paper,G
* will be a crisp graph (
V
,
E
) and G a vague graph (
A
,
B
) (see Figures 2 and 4). Since an edge x
y
∈
E is identified with an ordered pair (
x
,
y
)
∈
V
×
V, a vague relation on E can be identified with a vague set on E. This gives a possibility to define a vague graph as a pair of vague sets.Definition 5 (see [10]).
A vague relationB on a set V is a vague relation from V to V. If A is a vague set on a set V, then a vague relation B on A is a vague relation which satisfies
(2)
t
B
(
x
y
)
≤
min
⁡
(
t
A
(
x
)
,
t
A
(
y
)
)
,
f
B
(
x
y
)
≥
max
⁡
(
f
A
(
x
)
,
f
A
(
y
)
)
for all x, y
∈
V.Definition 6 (see [10]).
LetV be a nonempty set; members of V are callednodes. Avague graph
G
=
(
A
,
B
) with V as the set of nodes is a pair of functions A and B, where A is a vague set of V and B is a vague relation on V.We note that vague relationB in vague digraph need not be symmetric.Example 7.
Consider a graphG
*
=
(
V
,
E
) such that V
=
{
v
1
,
v
2
,
v
3
,
v
4
} and E
=
{
v
1
v
2
,
v
2
v
3
,
v
3
v
4
,
v
4
v
1
}. Let A be a vague set on V, and let B be a vague relation on V defined by Table 1.
By routine computations, it is easy to see from Figure1 that G
=
(
A
,
B
) is a vague digraph.Table 1
(a)
v
1
v
2
v
3
v
4
t
A
0.4
0.6
0.5
0.5
f
A
0.1
0.2
0.1
0.2
(b)
v
1
v
2
v
2
v
3
v
3
v
4
v
4
v
1
t
B
0.1
0.2
0.3
0.4
f
B
0.6
0.7
0.6
0.6Figure 1
Vague digraph.Figure 2
Vague graph.Definition 8.
Consider an intersection graphP
(
S
)
=
(
S
,
T
) of a crisp graph G
*
=
(
V
,
E
). Let A
1
=
(
t
A
1
,
f
A
1
) and B
1
=
(
t
B
1
,
f
B
1
) be vague sets on V and E and A
2
=
(
t
A
2
,
f
A
2
) and B
2
=
(
t
B
2
,
f
B
2
) on S and T, respectively. Then avague intersection graph of the vague graph G
=
(
A
1
,
B
1
) is a vague graph P
(
G
)
=
(
A
2
,
B
2
) such that (a)
t
A
2
(
S
i
)
=
t
A
1
(
v
i
), f
A
2
(
S
i
)
=
f
A
1
(
v
i
),
(b)
t
B
2
(
S
i
S
j
)
=
t
B
1
(
v
i
v
j
), f
B
2
(
S
i
S
j
)
=
f
B
1
(
v
i
v
j
)
for allS
i
,
S
j
∈
S, S
i
S
j
∈
T.Example 9.
Consider a graphG
*
=
(
V
,
E
), where V
=
{
v
1
,
v
2
,
v
3
} is the set of vertices and E
=
{
v
1
v
2
,
v
2
v
3
,
v
3
v
1
} is the set of edges. Consider G
=
(
A
1
,
B
1
), where A
1 and B
1 are vague set and vague relation on V, respectively. We define Table 2.
By routine computations, it is easy to see from Figure3 that G is a vague graph. Consider an intersection graph P
(
S
)
=
(
S
,
T
) such that
(3)
S
=
{
S
1
=
{
v
1
,
v
2
}
,
S
2
=
{
v
2
,
v
3
}
,
S
3
=
{
v
1
,
v
3
}
}
,
T
=
{
S
1
S
2
,
S
2
S
3
,
S
3
S
1
}
.
Let A
2
=
(
t
A
2
,
f
A
2
) and B
2
=
(
t
B
2
,
f
B
2
) be vague sets on S and T, respectively. Then, by routine computations, we have
(4)
t
A
2
(
S
1
)
=
t
A
1
(
v
1
)
=
0.2
,
t
A
2
(
S
2
)
=
t
A
1
(
v
2
)
=
0.3
,
t
A
2
(
S
3
)
=
t
A
1
(
v
3
)
=
0.4
,
f
A
2
(
S
1
)
=
f
A
1
(
v
1
)
=
0.3
,
f
A
2
(
S
2
)
=
f
A
1
(
v
2
)
=
0.4
,
f
A
2
(
S
3
)
=
f
A
1
(
v
3
)
=
0.5
,
t
B
2
(
S
1
S
2
)
=
t
B
1
(
v
1
v
2
)
=
0.1
,
t
B
2
(
S
2
S
3
)
=
t
B
1
(
v
2
v
3
)
=
0.1
,
t
B
2
(
S
3
S
1
)
=
t
B
1
(
v
3
v
1
)
=
0.1
,
f
B
2
(
S
1
S
2
)
=
f
B
1
(
v
1
v
2
)
=
0.6
,
f
B
2
(
S
2
S
3
)
=
f
B
1
(
v
2
v
3
)
=
0.7
,
f
B
2
(
S
3
S
1
)
=
f
B
1
(
v
3
v
1
)
=
0.6
.Table 2
(a)
v
1
v
2
v
3
t
A
1
0.2
0.3
0.4
f
A
1
0.3
0.4
0.5
(b)
v
1
v
2
v
2
v
3
v
3
v
1
t
B
1
0.1
0.2
0.1
f
B
1
0.5
0.7
0.6Figure 3
Vague intersection graph.Figure 4
Vague graph.By routine computations, it is easy to see thatP
(
G
) is a vague intersection graph.Proposition 10.
LetG
=
(
A
1
,
B
1
) be a vague graph of G
* and let P
(
G
)
=
(
A
2
,
B
2
) be a vague intersection graph of P
(
S
). Then (a)
a vague intersection graph is a vague graph;
(b)
a vague graph is isomorphic to a vague intersection graph.Proof.
(a) From Definition6, it follows that
(5)
t
B
2
(
S
i
S
j
)
=
t
B
1
(
v
i
v
j
)
≤
min
⁡
(
t
A
1
(
v
i
)
,
t
A
1
(
v
j
)
)
,
f
B
2
(
S
i
S
j
)
=
f
B
1
(
v
i
v
j
)
≥
max
⁡
(
f
A
1
(
v
i
)
,
f
A
1
(
v
j
)
)
.
This shows that a vague intersection graph is a vague graph.
(b) Defineφ
:
V
→
S by φ
(
v
i
)
=
s
i, for i
=
1,2
…
,
n. Clearly, φ is a one-to-one function of V onto S. Now v
i
v
j
∈
E if and only if s
i
s
j
∈
T and T
=
{
φ
(
v
i
)
φ
(
v
j
)
∣
v
i
v
j
∈
E
}. Also
(6)
t
A
2
(
φ
(
v
i
)
)
=
t
A
2
(
S
i
)
=
t
A
1
(
v
i
)
,
f
A
2
(
φ
(
v
i
)
)
=
f
A
2
(
S
i
)
=
f
A
1
(
v
i
)
,
t
B
2
(
φ
(
v
i
)
φ
(
v
j
)
)
=
t
B
2
(
S
i
S
j
)
=
t
B
1
(
v
i
v
j
)
,
f
B
2
(
φ
(
v
i
)
φ
(
v
j
)
)
=
f
B
2
(
S
i
S
j
)
=
f
B
1
(
v
i
v
j
)
.
Thus φ is an isomorphism of G onto P
(
G
).Definition 11.
LetL
(
G
*
)
=
(
Z
,
W
) be a line graph of a crisp graph G
*
=
(
V
,
E
). Let A
1
=
(
t
A
1
,
f
A
1
) and B
1
=
(
t
B
1
,
f
B
1
) be vague sets on V and E and A
2
=
(
t
A
2
,
f
A
2
) and B
2
=
(
t
B
2
,
f
B
2
) on Z and W, respectively. Then avague line graph of the vague graph G
=
(
A
1
,
B
1
) is a vague graph L
(
G
)
=
(
A
2
,
B
2
) such that (i)
t
A
2
(
S
x
)
=
t
B
1
(
x
)
=
t
B
1
(
u
x
v
x
),
(ii)
f
A
2
(
S
x
)
=
f
B
1
(
x
)
=
f
B
1
(
u
x
v
x
),
(iii)
t
B
2
(
S
x
S
y
)
=
min
⁡
(
t
B
1
(
x
)
,
t
B
1
(
y
)
),
(iv)
f
B
2
(
S
x
S
y
)
=
max
⁡
(
f
B
1
(
x
)
,
f
B
1
(
y
)
)
for allS
x
,
S
y
∈
Z
,
S
x
S
y
∈
W.Example 12.
Consider a crisp graphG
*
=
(
V
,
E
), where V
=
{
v
1
,
v
2
,
v
3
,
v
4
} is the set of vertices, and E
=
{
x
1
=
v
1
v
2
,
x
2
=
v
2
v
3
,
x
3
=
v
3
v
4
,
x
4
=
v
4
v
1
} is the set of edges. Let A
1 be a vague set on V and let B
1 be vague relation on V defined by Table 3.
By routine computations, it is easy to see thatG
=
(
A
1
,
B
1
) is a vague graph. Consider a line graph L
(
G
*
)
=
(
Z
,
W
) such that
(7)
Z
=
{
S
x
1
,
S
x
2
,
S
x
3
,
S
x
4
}
,
W
=
{
S
x
1
S
x
2
,
S
x
2
S
x
3
,
S
x
3
S
x
4
,
S
x
4
S
x
1
}
.
LetA
2
=
(
t
A
2
,
f
A
2
) and B
2
=
(
t
B
2
,
f
B
2
) be vague sets on Z and W, respectively. Then, by routine computations, we have
(8)
t
A
2
(
S
x
1
)
=
0.1
,
t
A
2
(
S
x
2
)
=
0.2
,
t
A
2
(
S
x
3
)
=
0.1
,
t
A
2
(
S
x
4
)
=
0.1
,
f
A
2
(
S
x
1
)
=
0.6
,
f
A
2
(
S
x
2
)
=
0.6
,
f
A
2
(
S
x
3
)
=
0.7
,
f
A
2
(
S
x
4
)
=
0.7
,
t
B
2
(
S
x
1
S
x
2
)
=
0.1
,
t
B
2
(
S
x
2
S
x
3
)
=
0.1
,
t
B
2
(
S
x
3
S
x
4
)
=
0.1
,
t
B
2
(
S
x
4
S
x
1
)
=
0.1
,
f
B
2
(
S
x
1
S
x
2
)
=
0.6
,
f
B
2
(
S
x
2
S
x
3
)
=
0.7
,
f
B
2
(
S
x
3
S
x
4
)
=
0.7
,
f
B
2
(
S
x
4
S
x
1
)
=
0.7
.Table 3
(a)
v
1
v
2
v
3
v
4
t
A
1
0.2
0.3
0.4
0.2
f
A
1
0.5
0.4
0.5
0.3
(b)
x
1
x
2
x
3
x
4
t
B
1
0.1
0.2
0.1
0.1
f
B
1
0.6
0.6
0.7
0.7By routine computations, it is clear thatL
(
G
)
=
(
A
2
,
B
2
) is a vague line graph (see Figure 5).Figure 5
Vague line graph.Remark 13.
L
(
G
)
=
(
A
2
,
B
2
) is a vague line graph corresponding to the vague graph G
=
(
A
1
,
B
1
).Proposition 14.
IfL
(
G
)
=
(
A
2
,
B
2
) is a vague line graph of a vague graph G
=
(
A
1
,
B
1
), then L
(
G
*
)
=
(
Z
,
W
) is the line graph of G
*
=
(
V
,
E
).Proposition 15.
L
(
G
)
=
(
A
2
,
B
2
) is a vague line graph of some vague graph G
=
(
A
1
,
B
1
) if and only if
(9)
t
B
2
(
S
x
S
y
)
=
min
⁡
(
t
A
2
(
S
x
)
,
t
A
2
(
S
y
)
)
,
f
B
2
(
S
x
S
y
)
=
max
⁡
(
f
A
2
(
S
x
)
,
f
A
2
(
S
y
)
)
for all S
x
,
S
y
∈
W.Proof.
Assume thatt
B
2
(
S
x
S
y
)
=
min
⁡
(
t
A
2
(
S
x
)
,
t
A
2
(
S
y
)
) for all S
x, S
y
∈
W. We define t
A
1
(
x
)
=
t
A
2
(
S
x
) for all x
∈
E. Then
(10)
t
B
2
(
S
x
S
y
)
=
min
⁡
(
t
A
2
(
S
x
)
,
t
A
2
(
S
y
)
)
=
min
⁡
(
t
A
1
(
x
)
,
t
A
1
(
y
)
)
,
f
B
2
(
S
x
S
y
)
=
max
⁡
(
f
A
2
(
S
x
)
,
f
A
2
(
S
y
)
)
=
max
⁡
(
f
A
1
(
x
)
,
f
A
1
(
y
)
)
.
A vague set A
1
=
(
t
A
1
,
f
A
1
) that yields the properties
(11)
t
B
1
(
x
y
)
≤
min
⁡
(
t
A
1
(
x
)
,
t
A
1
(
y
)
)
,
f
B
1
(
x
y
)
≥
max
⁡
(
f
A
1
(
x
)
,
f
A
1
(
y
)
)
will suffice.
The converse part is obvious.Another characterization of vague line graphs of vague graphs is given by the following proposition.Proposition 16.
L
(
G
)
=
(
A
2
,
B
2
) is a vague line graph of some vague graph if and only if L
(
G
*
)
=
(
Z
,
W
) is a line graph such that
(12)
t
B
2
(
u
v
)
=
min
⁡
(
t
A
2
(
u
)
,
t
A
2
(
v
)
)
,
f
B
2
(
u
v
)
=
max
⁡
(
f
A
2
(
u
)
,
f
A
2
(
v
)
)
for all u
v
∈
W.Definition 17.
LetG
1
=
(
A
1
,
B
1
) and G
2
=
(
A
2
,
B
2
) be two vague graphs. Ahomomorphism
φ
:
G
1
→
G
2 is a mapping φ
:
V
1
→
V
2 such that (a)
t
A
1
(
x
1
)
≤
t
A
2
(
φ
(
x
1
)
), f
A
1
(
x
1
)
≥
f
A
2
(
φ
(
x
1
)
),
(b)
t
B
1
(
x
1
y
1
)
≤
t
B
2
(
φ
(
x
1
)
φ
(
y
1
)
), f
B
1
(
x
1
y
1
)
≥
f
B
2
(
φ
(
x
1
)
φ
(
y
1
)
)
for allx
1
∈
V
1, x
1
y
1
∈
E
1, and φ
(
x
1
y
1
)
∈
E
2.
A bijective homomorphismφ
:
G
1
→
G
2 of vague graphs is called aweak vertex-isomorphism if (c)
t
A
1
(
x
1
)
=
t
A
2
(
φ
(
x
1
)
), f
A
1
(
x
1
)
=
f
A
2
(
φ
(
x
1
)
),
for allx
1
∈
V
1, and aweak line-isomorphism if (d)
t
B
1
(
x
1
y
1
)
=
t
B
2
(
φ
(
x
1
)
φ
(
y
1
)
), f
B
1
(
x
1
y
1
)
=
f
B
2
(
φ
(
x
1
)
φ
(
y
1
)
),
for allx
1
y
1
∈
E
1. A bijective homomorphism φ
:
G
1
→
G
2 satisfying (
c
) and (
d
) is called aweak isomorphism of vague graphs G
1 and G
2. 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 graphsG
1 and G
2 is an isomorphism of their crisp graphs G
1
* and G
2
*.Theorem 19.
LetL
(
G
)
=
(
A
2
,
B
2
) be the vague line graph corresponding to the vague graph G
=
(
A
1
,
B
1
). Suppose that G
*
=
(
V
,
E
) is connected. Then one has the following.(i)
There exists a weak isomorphism ofG onto L
(
G
) if and only if G
* is a cycle and for all v
∈
V, x
∈
E, t
A
1
(
v
)
=
t
B
1
(
x
), f
A
1
(
v
)
=
f
B
1
(
x
); that is, A
1
=
(
t
A
1
,
f
A
1
) and B
1
=
(
t
B
1
,
f
B
1
) are constant functions on V and E, respectively, taking on the same value.
(ii)
Ifφ is a weak isomorphism of G onto L
(
G
), then φ is an isomorphism.Proof.
Assume thatφ is a weak isomorphism of G onto L
(
G
). From Proposition 15, it follows that G
*
=
(
V
,
E
) is a cycle [18, Theorem 8.2, page 72]. Let V
=
{
v
1
,
v
2
,
…
,
v
n
} and E
=
{
x
1
=
v
1
v
2
,
x
2
=
v
2
v
3
,
…
,
x
n
=
v
n
v
1
}, where v
1
v
2
v
3
,
…
,
v
n is a cycle. Define vague sets
(13)
t
A
1
(
v
i
)
=
s
i
,
f
A
1
(
v
i
)
=
s
i
′
,
t
B
1
(
x
i
)
=
t
B
1
(
v
i
v
i
+
1
)
=
r
i
,
f
B
1
(
x
i
)
=
f
B
1
(
v
i
v
i
+
1
)
=
r
i
′
,
h
h
h
h
h
h
h
h
h
i
=
1,2
,
…
,
n
,
v
n
+
1
=
v
1
.
Then for s
n
+
1
=
s
1 and s
n
+
1
′
=
s
1
′, we have
(14)
r
i
≤
min
⁡
(
s
i
,
s
i
+
1
)
,
r
i
′
≥
max
⁡
(
s
i
′
,
s
i
+
1
′
)
,
h
h
h
i
=
1,2
,
…
,
n
.
Now
(15)
Z
=
{
S
x
1
,
S
x
2
,
S
x
3
,
…
,
S
x
n
}
,
W
=
{
S
x
1
S
x
2
,
S
x
2
S
x
3
,
…
,
S
x
n
S
x
1
}
.
Thus for r
n
+
1
=
r
1, we obtain
(16)
t
A
2
(
S
x
i
)
=
t
B
1
(
x
i
)
=
r
i
,
f
A
2
(
S
x
i
)
=
f
B
1
(
x
i
)
=
r
i
′
,
t
B
2
(
S
x
i
S
x
i
+
1
)
=
min
⁡
(
t
B
1
(
x
i
)
,
t
B
1
(
x
i
+
1
)
)
=
min
⁡
(
r
i
,
r
i
+
1
)
,
f
B
2
(
S
x
i
S
x
i
+
1
)
=
max
⁡
(
f
B
1
(
x
i
)
,
f
B
1
(
x
i
+
1
)
)
=
max
⁡
(
r
i
′
,
r
i
+
1
′
)
for i
=
1,2
,
…
,
n, v
n
+
1
=
v
1. Since φ is an isomorphism of G
* onto L
(
G
*
), φ is a bijective map of V onto Z. Also φ preserves adjacency. Hence φ induces a permutation π of {
1,2
,
…
,
n
} such that
(17)
φ
(
v
i
)
=
S
v
π
(
i
)
v
π
(
i
)
+
1
,
v
i
v
i
+
1
⟶
φ
(
v
i
)
φ
(
v
i
+
1
)
=
S
v
π
(
i
)
v
π
(
i
)
+
1
S
v
π
(
i
+
1
)
v
π
(
i
+
1
)
+
1
,
h
h
h
h
h
i
=
1,2
,
…
,
n
-
1
.
Thus
(18)
s
i
=
t
A
1
(
v
i
)
≤
t
A
2
(
φ
(
v
i
)
)
=
t
A
2
(
S
v
π
(
i
)
v
π
(
i
)
+
1
)
=
t
B
1
(
v
π
(
i
)
v
π
(
i
)
+
1
)
=
r
π
(
i
)
,
s
i
′
=
f
A
1
(
v
i
)
≥
f
A
2
(
φ
(
v
i
)
)
=
f
A
2
(
S
v
π
(
i
)
v
π
(
i
)
+
1
)
=
f
B
1
(
v
π
(
i
)
v
π
(
i
)
+
1
)
=
r
π
(
i
)
′
,
r
i
=
t
B
1
(
v
i
v
i
+
1
)
≤
t
B
2
(
φ
(
v
i
)
φ
(
v
i
+
1
)
)
=
t
B
2
(
S
v
π
(
i
)
v
π
(
i
)
+
1
S
v
π
(
i
+
1
)
v
π
(
i
+
1
)
+
1
)
=
min
⁡
(
t
B
1
(
v
π
(
i
)
v
π
(
i
)
+
1
)
,
t
B
1
(
v
π
(
i
+
1
)
v
π
(
i
+
1
)
+
1
)
)
=
min
⁡
(
r
π
(
i
)
,
r
π
(
i
+
1
)
)
.
Similarly,
(19)
r
i
′
=
f
B
1
(
v
i
v
i
+
1
)
≥
f
B
2
(
φ
(
v
i
)
φ
(
v
i
+
1
)
)
=
f
B
2
(
S
v
π
(
i
)
v
π
(
i
)
+
1
S
v
π
(
i
+
1
)
v
π
(
i
+
1
)
+
1
)
=
max
⁡
(
f
B
1
(
v
π
(
i
)
v
π
(
i
)
+
1
)
,
f
B
1
(
v
π
(
i
+
1
)
v
π
(
i
+
1
)
+
1
)
)
=
max
⁡
(
r
π
(
i
)
′
,
r
π
(
i
+
1
)
′
)
for i
=
1,2
,
…
,
n. That is,
(20)
s
i
≤
r
π
(
i
)
,
s
i
′
≥
r
π
′
(
i
)
,
(21)
r
i
≤
min
⁡
(
r
π
(
i
)
,
r
π
(
i
+
1
)
)
,
r
i
′
≥
max
⁡
(
r
π
(
i
)
′
,
r
π
(
i
+
1
)
′
)
.
Thus,r
i
≤
r
π
(
i
) and r
i
′
≥
r
π
(
i
)
′ and so r
π
(
i
)
≤
r
π
(
π
(
i
)
)and r
π
(
i
)
′
≥
r
π
(
π
(
i
)
)
′ for all i
=
1,2
,
…
,
n. Continuing, we obtain
(22)
r
i
≤
r
π
(
i
)
≤
⋯
≤
r
π
j
(
i
)
≤
r
i
,
r
i
′
≥
r
π
(
i
)
′
≥
⋯
≥
r
π
j
(
i
)
′
≥
r
i
′
,
where π
j
+
1 is the identity map. So, r
i
=
r
π
(
i
) and r
i
′
=
r
π
(
i
)
′ for all i
=
1,2
,
…
,
n. But, by (21), we also have r
i
≤
r
π
(
i
+
1
)
=
r
i
+
1 and r
i
′
≥
r
π
(
i
+
1
)
′
=
r
i
+
1
′, which together with r
n
+
1
=
r
1 and r
n
+
1
′
=
r
1
′ imply r
i
=
r
1 and r
i
′
=
r
1
′ for all i
=
1,2
,
…
,
n. Hence by (14) and (20), we get
(23)
r
1
=
⋯
=
r
n
=
s
1
=
⋯
=
s
n
,
r
1
′
=
⋯
=
r
n
′
=
s
1
′
=
⋯
=
s
n
′
.
Thus we have not only proven the conclusion about A
1 and B
1 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.
LetG and H be vague graphs of G
* and H
*, respectively, such that G
* and H
* are connected. Let L
(
G
*
) and L
(
H
*
) be the line graphs corresponding to G and H, respectively. Suppose that it is not the case that one of G
* and H
* is complete graph K
3 and the other is bipartite complete graph K
1,3. If L
(
G
) and L
(
H
*
) are isomorphic, then G and H are line-isomorphic.


## 4. Regular Vague Intersection Graphs and Vague Line Graphs

Definition 21.
A vague graphG is calledcompleteif
(24)
t
B
(
x
y
)
=
min
⁡
(
t
A
(
x
)
,
t
A
(
y
)
)
,
f
B
(
x
y
)
=
max
⁡
(
f
A
(
x
)
,
f
A
(
y
)
)
for each edge x
y
∈
E.Example 22.
Consider a vague graphG.Routine computations show thatG is complete (see Figure 6).Figure 6
G is complete.Definition 23.
LetG be a vague graph on G
*. If all the vertices have the same open neighbourhood degree m, then G is called aregular vague graph. The neighbourhood degree of a vertex x in G is defined by deg
⁡
(
x
)
=
(
deg
⁡
t
(
x
)
,
deg
⁡
f
(
x
)
), where deg
⁡
t
(
x
)
=
∑
y
∈
N
(
x
)
‍
t
A
(
y
) and deg
⁡
f
(
x
)
=
∑
y
∈
N
(
x
)
‍
f
A
(
y
).Definition 24.
LetG be a vague graph. The closed neighbourhood degree of a vertex x is defined by deg
⁡
[
x
]
=
(
deg
⁡
t
[
x
]
,
deg
⁡
f
[
x
]
), where
(25)
deg
⁡
t
[
x
]
=
deg
⁡
t
(
x
)
+
t
A
(
x
)
,
deg
⁡
f
[
x
]
=
deg
⁡
f
(
x
)
+
f
A
(
x
)
.
If each vertex of G has the same closed neighbourhood degree m, then G is called atotally regular vague graph.Example 25.
Consider a graphG
* such that V
=
{
v
1
,
v
2
,
v
3
} and E
=
{
v
1
v
2
,
v
2
v
3
,
v
3
v
1
}. Let A be a vague subset of V and let B be a vague subset of V defined by
(26)
t
A
(
v
1
)
=
0.4
,
t
A
(
v
2
)
=
0.4
,
t
A
(
v
3
)
=
0.4
,
f
A
(
v
1
)
=
0.1
,
f
A
(
v
2
)
=
0.1
,
f
A
(
v
3
)
=
0.1
,
t
B
(
v
1
v
2
)
=
0.3
,
t
B
(
v
2
v
3
)
=
0.3
,
t
B
(
v
3
v
1
)
=
0.3
,
f
B
(
v
1
v
2
)
=
0.6
,
f
B
(
v
2
v
3
)
=
0.6
,
f
B
(
v
3
v
1
)
=
0.6
.
Routine computations show that a vague graphG is both regular and totally regular.Definition 26.
If there is a vertex which is adjacent to vertices with distinct open neighbourhood degrees, thenG is called anirregular vague graph (see Figure 8). That is, deg
⁡
(
x
)
≠
m for all x
∈
V. If there is a vertex which is adjacent to vertices with distinct closed neighbourhood degrees, then G is called atotally irregular vague graph (see Figure 9).Example 27.
Consider a graphG
* such that
(27)
V
=
{
v
1
,
v
2
,
v
3
}
,
E
=
{
v
1
v
2
,
v
2
v
3
,
v
1
v
3
}
.
Let A be a vague subset of V and let B be a vague subset of V defined by Table 4.Table 4
(a)
v
1
v
2
v
3
t
A
0.2
0.2
0.3
f
A
0.6
0.7
0.4
(b)
v
1
v
2
v
1
v
3
v
2
v
3
t
B
0.1
0.1
0.2
f
B
0.2
0.2
0.3By routine computations, we havedeg
⁡
(
v
1
)
=
(
0.5,1.1
), deg
⁡
(
v
2
)
=
(
0.5,1.0
), and deg
⁡
(
v
3
)
=
(
0.4,1.3
). It is clear that G is an irregular vague graph.Example 28.
Consider a graphG
* such that V
=
{
a
,
b
,
c
,
d
} and E
=
{
a
b
,
b
c
,
c
d
,
a
d
}. Let A be a vague subset of V and let B be a vague subset of V defined by Table 5.
Routine computations show that a vague graphG is both irregular and totally irregular.Table 5
(a)
a
b
c
d
t
A
0.5
0.4
0.7
0.5
f
A
0.3
0.2
0.3
0.5
(b)
a
b
b
c
c
d
d
a
t
B
0.2
0.4
0.2
0.4
f
B
0.6
0.6
0.6
0.6Remark 29.
In classical (crisp) graph theory, any complete graphK
n is regular, but a complete vague graph G is not regular, in general (see Figure 10).Example 30.
Consider a graphG
* such that V
=
{
x
,
y
,
z
} and E
=
{
x
y
,
y
z
,
z
x
}. Let A be a vague subset of V and let B be a vague subset of V defined by
(28)
t
A
(
x
)
=
0.5
,
t
A
(
y
)
=
0.4
,
t
A
(
z
)
=
0.3
,
f
A
(
x
)
=
0.3
,
f
A
(
y
)
=
0.4
,
f
A
(
z
)
=
0.5
,
t
B
(
x
y
)
=
0.4
,
t
B
(
y
z
)
=
0.3
,
t
B
(
z
x
)
=
0.3
,
f
B
(
x
y
)
=
0.4
,
f
B
(
y
z
)
=
0.5
,
f
B
(
z
x
)
=
0.5
.
Clearly,G is a complete vague graph, but G is not regular since deg
⁡
(
x
)
≠
deg
⁡
(
z
).Definition 31 (see [10]).
The complement of a vague graphG
=
(
A
,
B
) of G
*
=
(
V
,
E
) is a vague graph G
¯
=
(
A
¯
,
B
¯
) on G
*
¯, where A
¯
=
(
t
A
-
,
f
A
-
) and B
¯
=
(
t
B
-
,
f
B
-
) are defined by (i)
(29)
V
¯
=
V
,
(ii)
(30)
t
A
¯
(
x
)
=
t
A
(
x
)
,
f
A
¯
(
x
)
=
f
A
(
x
)
∀
x
∈
V
,
(iii)
(31)
t
B
¯
(
x
y
)
=
{
0
if
t
B
(
x
y
)
>
0
,
min
⁡
(
t
A
(
x
)
,
t
A
(
y
)
)
if
t
B
(
x
y
)
=
0
,
f
B
¯
(
x
y
)
=
{
0
if
f
B
(
x
y
)
>
0
,
max
⁡
(
f
A
(
x
)
,
f
A
(
y
)
)
if
f
B
(
x
y
)
=
0
.Definition 32.
A vague graphG is calledself-complementary if G
¯
≈
G.Example 33.
Consider a vague graphG. (1)
Clearly, graphG is not isomorphic to its complement G
¯. Hence G is not self-complementary.
(2)
Routine calculations show thatG and G
¯ are irregular and totally irregular, respectively (see Figures 11 and 12).Example 34.
Consider a vague graphG. (1)
Clearly,G is isomorphic to its complement G
¯. Hence G is self-complementary.
(2)
Routine calculations show thatG and G
¯ are irregular and totally irregular, respectively.Theorem 35.
LetG
=
(
A
,
B
) be a vague graph of a graph G
*. Then A
=
(
t
A
,
f
A
) is a constant function if and only if the following are equivalent: (a)
G is a regular vague graph,
(b)
G is a totally regular vague graph.Proof.
LetA
=
(
t
A
,
f
A
) be a constant function. To prove that (
a
) and (
b
) are equivalent, suppose that t
A
(
x
)
=
c
1 and f
A
(
x
)
=
c
2 for all x
∈
V.
(
a
)
⇒
(
b
): If a vague graph G is n-regular, then deg
⁡
t
(
x
)
=
n
1 and deg
⁡
f
(
x
)
=
n
2 for all x
∈
V. So
(32)
deg
⁡
t
[
x
]
=
deg
⁡
t
(
x
)
+
t
A
(
x
)
,
deg
⁡
f
[
x
]
=
deg
⁡
f
(
x
)
+
f
A
(
x
)
hhhhhhhhhhhhhhh
∀
x
∈
V
.
Thus
(33)
deg
⁡
t
[
x
]
=
n
1
+
c
1
,
deg
⁡
f
[
x
]
=
n
2
+
c
2
hhhhhhhh
∀
x
∈
V
.
Hence, G is totally regular.
(
b
)
⇒
(
a
): Suppose that G is totally regular. Then for all x
∈
V, we have
(34)
k
1
=
deg
⁡
t
[
x
]
=
deg
⁡
t
(
x
)
+
t
A
(
x
)
=
deg
⁡
t
(
x
)
+
c
1
.
Hence,
(35)
deg
⁡
t
(
x
)
=
k
1
-
c
1
for
every
x
∈
V
.
Similarly we obtain deg
⁡
f
(
x
)
=
k
2
-
c
2 for every x
∈
V, where k
2
=
deg
⁡
f
[
x
]. This means that G is regular (see Figure 7).
Hence(
a
) and (
b
) are equivalent.
The converse part is obvious.Figure 7
G is regular and totally regular.Figure 8
G is irregular.Figure 9
G is irregular and totally irregular.Figure 10
G is complete but not regular.Figure 11
G and G
¯ are irregular and totally irregular.Figure 12
G and G
¯ are irregular and totally irregular.Example 36.
Consider a graphG
* such that V
=
{
v
1
,
v
2
,
v
3
} and E
=
{
v
1
v
2
,
v
1
v
3
}. Let A and B be vague subsets defined by
(36)
t
A
(
v
1
)
=
t
A
(
v
2
)
=
t
A
(
v
3
)
=
0.4
,
f
A
(
v
1
)
=
f
A
(
v
2
)
=
f
A
(
v
3
)
=
0.1
,
t
B
(
v
1
v
2
)
=
0.2
,
t
B
(
v
1
v
3
)
=
0.1
,
f
B
(
v
1
v
2
)
=
0.2
,
f
B
(
v
1
v
3
)
=
0.2
.
Clearly, A
=
(
t
A
,
f
A
) is constant and G 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 Example9. Routine calculations show that P
(
G
) is an irregular vague intersection graph, but it is totally regular vague intersection graph.Example 38.
Consider vague line graph which is given in Example12. Routine calculations show that L
(
G
) 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 vertexx to vertex y, when the person represented by vertex x influences the person represented by vertex y. 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 Figure13, 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.Figure 13
Vague influence graph.The degree of a vertex and edge in a vague influence graph is also characterized by an interval[
t
A
(
x
)
,
1
-
f
A
(
x
)
]. 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 x” only, without considering “evidence against x.” 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 t
A
=
60
% to 1
-
f
A
=
80
% power, whereas the edges show the interval of influence a person has on another person in a social group. Tanzel has t
A
=
30
% to 1
-
f
A
=
40
% influence on Amir and Amir has t
A
=
40
% to 1
-
f
A
=
40
% influence on Rajab.


## 6. Conclusions

In 1965, Zadeh introduced the concept of fuzzy sets by extending the range of Eigenfunction of classical sets from{
0,1
} to a closed interval [
0
,
1
]. However, the membership function of a fuzzy set is a single-valued function, which cannot express either the evidence for x
∈
X or the evidence against x
∈
X. 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 [
0
,
1
], 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.



---

*Source: 525389-2014-04-15.xml*