Domination in vague graphs and its applications

Abstract

The concept of vague graph introduced by Ramakrishna in [8]. The main purpose of this paper is to introduce the concepts of cardinality, dominating set, independent set, total dominating number and independent dominating number of a vague graph. The notion of irredundance number of a vague graph is discussed, too. Finally we give an application of domination in vague graphs.

Keywords

Vague graph strong edge dominating set independence number

1 Introduction

Graph theory is an extremely useful tool in solving combinatorial problems in different areas including geometry, algebra, number theory, topology, operations research, biology and social systems. Fuzzy graph theory is finding an increasing number of application in modeling real time systems where the level of information inherent in the system varies with different levels of precision. In 1965, Zadeh [20] first proposed the theory of fuzzy sets. Gau and Buehrer [4] proposed the concept of vague set in 1993, by replacing the value of an element in a set with a subinterval of [0, 1]. Namely, a true-membership function t_v (x) and a false membership function f _v (x) are used to describe the bounderies of the membership degree. The first definition of fuzzy graphs was proposed by Kafmann [5] in 1993, from Zadeh’s fuzzy relations [21], [22] and [20]. But Rosenfeld [9] introduced another elaborated definition including fuzzy vertex and fuzzy edges and several fuzzy analogs of graph theoretic concepts such as paths, cycles, connectedness and etc. Ramakrishna [8] introduced the concept of vague graphs and studied some of their properties. Akram et al. [1, 2] introduced the vague hypergraphs and some properties of vague graphs. Samanta and Pal introduced fuzzy planar graphs [16], fuzzy tolerance graphs [14], fuzzy threshold graphs [15], fuzzy k-competition graphs and p-competition fuzzy graphs [17], irregular bipolar fuzzy graphs [18]. A. Somasundaram and S. Somasundaram [19] defined domination in fuzzy graphs. Domination in intuitionistic fuzzy graphs introduced by Parvathi and Thamizhendhi [7]. Debnath [3] investigated domination in interval-valued fuzzy graphs. Pal and Rashmanlou studied irregular inteval-valued fuzzy graphs [6]. Also, they defined antipodal interval-valued fuzzy graphs [10], balanced interval-valued fuzzy graphs [11] and a study on bipolar fuzzy graphs [13]. Rashmanlou and Yong Bae Jun investigated complete interval-valued fuzzy graphs [12]. In this paper, we introduce the concepts of cardinality, dominating set, independent set, total dominating number and independent dominating number of vague graphs. The notion of a irredundance number of a vague graph is discussed also.

2 Preliminaries

A graph is an ordered pair G = (V, E), where V is the set of vertices of G and E is the set of edges of G. A subgraph of a graph G = (V, E) is a graph H = (W, F), where W ⊆ V and F ⊆ E. A fuzzy graph G = (σ, μ) is a pair of functions σ : V → [0, 1] and μ : V × V → [0, 1] with μ (u, v) ≤ σ (u) ∧ σ (v) for all u, v ∈ V, where V is a finite non-empty set and ∧ denote minimum.

A vague set A in an ordinary finite non-empty set 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 0 ≤ t _A (x) + f _A (x) ≤1 for all x ∈ X. Note that t _A (x) is considered as the lower bound for degree of membership of x in A and f _A (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 the interval [t _A (x) , 1 - f _A (x)]. Hence, a vague set is a special case of interval valued sets studied by many mathematicians and applied in many branches of mathematics. Let X and Y be two ordinary finite non-empty sets. We call a vague relation to be a vague subset of X × Y, that is an expression Rdefined by $R = {〈 (x, y), t_{R} (x, y), f_{R} (x, y) 〉 | x \in X, y \in Y}$ where t _R : X × Y → [0, 1] , 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. (See [2])

Definition 2.1. [8] A vague graph is defined to be a pair G = (A, B), where A = (t _A, f _A) is a vague set on V and B = (t _B, f _B) is a vague set on E ⊆ V × V such that t _B (xy) ≤ min(t _A (x) , t _A (y)) and f _B (xy) ≥ max(f _A (x) , f _A (y)) for each edge xy ∈ E.

The underlying crisp graph of a vague graph G = (A, B), is the graph G = (V, E), where V = {v : t _A (v) >0 and f _A (v) >0} and E = {{u, v} :t _B ({u, v}) >0, f _B ({u, v}) >0}. V is called the vertex set and E is called the edge set. A vague graph may be also denoted as G = (V, E).

A vague graph G is said to be strong if t _B (v _i v _j) = min {t _A (v _i) , t _A (v _j)} and f _B (v _i v _j) = max {f _A (v _i) , f _A (v _j)} for every edge v _i v _j ∈ E. A vague graph G is said to be complete if t _B (v _i v _j) = min {t _A (v _i) , t _A (v _j)} and f _B (v _i v _j) = max {f _A (v _i) , f _A (v _j)} for all v _i, v _j ∈ V.

A vague graph G = (V, E) is said to be n-partite (multipartite) if the vertex set V can be partitioned into n subsets V ₁, V ₂, ⋯ , V _n such that:

For every v _i, v _j ∈ V _i and 1 ≤ i, j ≤ n, we have $t_{B} (v_{i} v_{j}) = 0 and f_{B} (v_{i} v_{j}) = 0 .$

For every v _i ∈ V _i, v _j ∈ V _j and 1 ≤ i, j ≤ n, we have $t_{B} (v_{i} v_{j}) = 0, f_{B} (v_{i} v_{j}) > 0 or$ $t_{B} (v_{i} v_{j}) > 0, f_{B} (v_{i} v_{j}) = 0 .$

A path P in a vague graph G is a sequence of distinct vertices v ₁, v ₂, ⋯ , v _n such that either one of the following conditions is satisfied:

t _B (v _i v _j) >0 and f _B (v _i v _j) =0 for some i, j,

t _B (v _i v _j) =0 and f _B (v _i v _j) >0 for some i, j,

t _B (v _i v _j) =0 and f _B (v _i v _j) =0 for some i, j.

A vague graph G is connected if any two vertices are joined by a path. The t-strength of a path P : v ₁, v ₂, ⋯ , v _n is defined as min(t _B (v _i v _j)) for all i, j and is denoted by S _t. The f-strength of a path P : v ₁, v ₂, ⋯ , v _n is defined as max(f _B (v _i v _j)) for all i, j and is denoted by S _f. If the same edge possesses both t-strength and f-strength value, then it is the strength of a path P. The strength of a path is (t _B (v _i v _j) , f _B (v _i v _j)) = (S _t, S _f). Note that the t-strength of the path connecting any two vertices v _i, v _j is defined as max(S _t) and is denoted by (t _B (v _i v _j)) ^∞ and the f-strength of the path connecting any two vertices v _i, v _j is defined as min(S _f) and is denoted by (S _f (v _i v _j)) ^∞. If the same edge possesses both t-strength and f-strength value, then it is the strength of the strongest path P and it is denoted by S _p = ((t _B (v _i v _j)) ^∞, (f _B (v _i v _j)) ^∞) for all i, j = 1, 2, ⋯ , n. (See [2])

Definition 2.2. [2] Let G = (A, B) be a vague graph.

The cardinality of G is defined to be $\begin{matrix} | G | & = & | \sum_{v_{i} \in V} \frac{1 + t_{A} (v_{i}) - f_{A} (v_{i})}{2} \\ + \sum_{v_{i} v_{j} \in E} \frac{1 + t_{B} (v_{i} v_{j}) - f_{B} (v_{i} v_{j})}{2} | . \end{matrix}$

The vertex cardinality of G is defined by $| V | = \sum_{v_{i} \in V} \frac{1 + t_{A} (v_{i}) - f_{A} (v_{i})}{2}$

for all v _i ∈ V.

The edge cardinality of G is defined by $| E | = \sum_{v_{i} v_{j} \in E} (\frac{1 + t_{B} (v_{i} v_{j}) - f_{B} (v_{i} v_{j})}{2})$

for all v _i v _j ∈ E.

The number of vertices (the cardinality of V) is called the order of a vague graph and is denoted by $O (G) = \sum_{v_{i} \in V} (\frac{1 + t_{A} (v_{i}) - f_{A} (v_{i})}{2})$

for all v _i ∈ V.

The number of edges (the cardinality of E) is called the size of a vague graph and is denoted by $S (G) = \sum_{v_{i} v_{j} \in E} (\frac{1 + t_{B} (v_{i} v_{j}) - f_{B} (v_{i} v_{j})}{2})$

for all v _i v _j ∈ E.

The degree of a vertex v in a vague graph G is defined to be sum of the weights of the strong edges incident at v. It is denoted by d _G (v). The minimum degree of G is δ (G) = min {d _G (v) | v ∈ V}. The maximum degree of G is ▵ (G) = max {d _G (v) | v ∈ V}.

Definition 2.3. [2] The complement of a vague graphG = (A, B) is a vague graph $\bar{G} = (\bar{A}, \bar{B})$ where $\bar{A} = A$ , $\bar{t_{B}} (v_{i} v_{j}) = min (t_{A} (v_{i}), t_{A} (v_{j})) - t_{B} (v_{i} v_{j})$ and $\bar{f_{B}} (v_{i} v_{j}) = max (f_{A} (v_{i}), f_{A} (v_{j})) - f_{B} (v_{i} v_{j})$ .

3 Domination in vague graphs

Domination in graphs has applications to several fields. Domination arises in facility location problems, where the number of facilities (e.g., hospitals, fire stations) is fixed and one attempts to minimize the distance that a person needs to travel to get to the closest facility. A similar problem occurs when the maximum distance to a facility is fixed and one attempts to minimize the number of facilities necessary so that everyone is serviced. Concepts from domination also appear in problems involving finding sets of representatives, in monitoring communication or electrical networks, and in land surveying (e.g., minimizing the number of places a surveyor must stand in order to take height measurements for an entire region). In this section, we define the concepts of cardinality, dominating set, independent set, total dominating number and independent dominating number of vague graphs.

Definition 3.1. An edge (u, v) is said to be strong edge in vague graph G = (A, B) if t _B (uv) ≥ (t _B) ^∞(uv) and f _B (uv) ≤ (f _B) ^∞ (uv), where (t _B) ^∞ (uv) = max {(t _B) ^k (uv) | k = 1, 2, ⋯ , n} and (f _B) ^∞ (uv) = min {(f _B) ^k (uv) | k = 1, 2, ⋯ , n}.

Definition 3.2. Let u be a vertex in a vague graphG = (A, B). Then $N (u) = {v : v \in V and (u, v) is a strong edge in G}$ is called neighborhood of u in G. A vertex u ∈ V of a vague graph G is said to be an isolated vertex ift _B (uv) =0 and f _B (uv) =0, for all v ∈ V, u ≠ v, that is N (u) =∅. Hence, an isolated vertex does not dominate any other vertex of G.

Let G = (A, B) be an interval-valued fuzzy graph and u, v ∈ V. We say that u dominate v in G if $μ_{B}^{-} (u v) = min {μ_{A}^{-} (u), μ_{A}^{-} (v)}$ and $μ_{B}^{+} (u v) = max {μ_{A}^{+} (u), μ_{A}^{+} (v)}$ . (See [3])

Now domination in vague graph is as follows.

Definition 3.3. Let G = (A, B) be a vague graph. Let u, v ∈ V, we say that u dominate v in G if there exists a strong edge between them.

Not 3.4. (i) For any u, v ∈ V, if u dominates v then v dominates u. Hence domination is a symmetric relation on V.

For any v ∈ V, N (v) is precisely the set of all vertices in V which are dominated by v.

If t _B (uv) < (t _B) ^∞ (uv) and f _B (uv) > (f _B) ^∞(uv) for all u, v ∈ V, then the dominating set of G is V.

Definition 3.5. (i) A subset S of V is called a dominating set in G if for every v ∈ V - S, there exists u ∈ S such that u dominates v.

A dominating set S of a vague graph is said to be minimal dominating set if no proper subset of S is a dominating set.

Minimum cardinality among all minimal dominating set is called lower domination number of G, and is denoted by d _V (G).

Maximum cardinality among all minimal dominating set is called upper domination number of G, and is denoted by D _V (G).

Example 3.6. Consider a vague graph G = (V, E) such that V = {u ₁, u ₂, u ₃, u ₄, u ₅} and E = {(u ₁, u ₂) , (u ₂, u ₃) , (u ₃, u ₄) , (u ₄, u ₅) , (u ₅, u ₁) , (u ₁, u ₄) , (u ₂, u ₄)}.

In Fig. 1,{u ₂, u ₅} , {u ₁, u ₃, u ₅}, and {u ₁, u ₂, u ₃, u ₅} are three dominating sets, {(u ₁, u ₄)} is a minimal dominating set of minimal cardinality and d _V (G) =0.55, {(u ₂, u ₃)} is a minimal dominating set of maximal cardinality and D _V (G) =0.8.

Definition 3.7. Two vertices in a vague graph G = (V, E) called independent if there is no any strong edge between them.

Definition 3.8. (i) A subset S of V is said to be independent set if t _B (uv) < (t _B) ^∞ (uv) and f _B (uv) > (f _B) ^∞ (uv), for all u, v ∈ S

An independent set S of vague graph G = (A, B), is said to be maximal independent, if for every vertex v ∈ V - S, the set S ∪ {v} is not independent.

The minimum cardinality among all maximal independent set is called lower independent number of G, and it is denoted by i _V (G).

The maximum cardinality among all maximal independent set is called upper independent number of G, and it is denoted by I _V (G).

Example 3.9. Consider a vague graph G = (V, E) such that V = {u ₁, u ₂, u ₃, u ₄} and E = {(u ₁, u ₂) , (u ₂, u ₃) , (u ₁, u ₃) , (u ₃, u ₄) , (u ₂, u ₄)}.

In Fig. 2, { {u ₁, u ₂} , {u ₂, u ₃}} is independent set, {u ₂, u ₃} is a maximal independent set of minimal cardinality and i _V (G) =0.9, {u ₁, u ₂} is a maximal independent set of maximal cardinality and I _V (G) =0.95.

Theorem 3.10.A dominating set D of a vague graph G = (V, E) is a minimal dominating set if and only if for each d ∈ D one of the following conditions holds.

d is not a strong neighbor of any vertex in D.

There is a vertex v ∈ V - D such that N (v) ∩ D = d.

Proof. Assume that D is a minimal dominating set of G. Then for every vertex d ∈ D, D - d is not a dominating set and hence there exists v ∈ V - (D - {d}) which is not dominated by any vertex in D - {d}. If v = d, then v is not a strong neighbor of any vertex in D. If v ≠ d, then v is not dominated by D - {v}, but is dominated by D. Then the vertex v is a strong neighbor only to d in D. That is, N (v) ∩ D = d. Conversely, assume that D is a dominating set and for each vertex d ∈ D, one of the two conditions holds. Suppose D is not a minimal dominating set. Then there exists a vertex d ∈ D, such that D - {d} is a dominating set. Hence d is a strong neighbor to at least one vertex in D - {d}, and so (i) does not hold. If D - {d} is a dominating set, then every vertex in V - D is a strong neighbor to at least one vertex in D - {d}, and so (ii) does not hold, which is a contradiction since at least one of the conditions should be hold. So D is a minimal dominating set.□

Theorem 3.11. Let G = (V, E) be a vague graph without isolated vertices and D be a minimal dominating set. Then V - D is a dominating set of G.

Proof. Let D be a minimal dominating set and d be a vertex of D. Since G has no isolated vertices, there exists a vertex v ∈ N (d) which is dominated by at least one vertex in D - {d}, that is D - {d} is a dominating set. By Theorem 3.10, it follows that v ∈ V - D. Thus every vertex in D is dominated by at least one vertex in V - D, and V - D is a dominating set.□

Theorem 3.12. For any vague graph G = (V, E), $d_{V} (G) + d_{V} (\bar{G}) < 2 O (G)$ , where $d_{V} (\bar{G})$ is the lower domination number of $\bar{G}$ and the equality holds if and only if 0 < t _B (v _i v _j) < (t _B) ^∞ (v _i v _j) and 0 > f _B (v _i v _j) > (f _B) ^∞ (v _i v _j), for all v _i, v _j ∈ V.

Proof. The result is trivial when $d_{V} (G) + d_{V} (\bar{G}) < 2 O (G)$ . d _V (G) = O (G) if and only if t _B (v _i v _j) < (t _B) ^∞(v _i v _j) and f _B (v _i v _j) > (f _B) ^∞ (v _i v _j), for all v _i, v _j ∈ V. $d_{V} (\bar{G}) = O (G)$ if and only if $\bar{t_{B}} (v_{i} v_{j}) - t_{B} (v_{i} v_{j}) < (t_{B})^{\infty} (v_{i} v_{j})$ and $\bar{f_{B}} (v_{i} v_{j}) - f_{B} (v_{i} v_{j}) > (f_{B})^{\infty} (v_{i} v_{j})$ , for all v _i, v _j ∈ V which gives t _B (v _i v _j) >0 and f _B (v _i v _j) <0. Hence $d_{V} (G) + d_{V} (\bar{G}) \leq 2 O (G)$ .□

Remark 3.13. For any vague graph G = (V, E) without isolated vertices, $d_{V} (G) = \frac{O (G)}{2}$ .

Theorem 3.14. For any vague graph G = (V, E), there exists ▵ ∈ N such that d _V (G)≤ O (G) - ▵.

Proof. Let v be a vertex in vague graph G = (V, E). Assume that |N (v) | =▵. Then V - N (v) is a dominating set of G, and so d _V (G) ≤ |V - N (v) |= O (G) -▵.□

Theorem 3.15.An independent set of a vague graph G = (V, E) is a maximal independent set if and only if it is independent and dominating set.

Proof. Let D be a maximal independent set in vague graph G = (V, E). Then, for every vertex v ∈ V - D, the set D ∪ {v} is not independent. Moreover for every vertex v ∈ V - D, there is vertex u ∈ D such that u is strong neighbor to v and so D is a dominating set. Hence, D is both dominating and independent set.

Conversely, assume that D is both independent and dominating set, but D is not a maximal independent. Then there exists a vertex v ∈ V - D, which the set D ∪ {v} is independent. If D ∪ {v} is independent, then no any vertex in D is a strong neighbor to v. Hence D can not be a dominating set, which is a contradiction. Therefore, D is a maximal independent set.□

Theorem 3.16. Every maximal independent set in a vague graph G = (V, E) is a minimal dominating set.

Proof. Let S be a maximal independent set in vague graph G = (V, E). By Theorem 3.15, S is a dominating set. Suppose S is not minimal dominating. Then there exists at least one vertex v ∈ S such that S - {v} is a dominating set. But if S - {v} dominates V - {S - (v)}, then at least one vertex in S - (v) must be strong neighbor to v. This contradicts the fact that S is an independent set of G. Therefore, S must be a minimal dominating set.□

Definition 3.17. Let G = (V, E) be a vague graph without isolated vertices.

A set S is called a total dominating set if for every vertex v ∈ V, there exists a vertex u ∈ S, such that u ≠ v and u dominates v.

A total dominating set S is said to be minimal total dominating set if there is no any proper subset of S which is a total dominating set.

The minimum cardinality of a minimal total dominating set is called lower total dominating number of G, and it is denoted by t _V (G).

The maximum cardinality of minimal total dominating set is called upper total dominating number of G, and it is denoted by T _V (G).

Example 3.18. In Fig.1, {u ₃, u ₄, u ₅} and {u ₁, u ₂, u ₄} are two total dominating sets. {u ₃, u ₄, u ₅} is the only minimal total dominating set. Hence, we have t _V (G) = T _V (G) =1.05.

Theorem 3.19. For a vague graph G = (V, E), t _V (G) = O _V (G) if and only if every vertex of G has a unique neighbor.

Proof. If every vertex of G has a unique neighbor, then vertex set V is the only total dominating set of G and so t _V (G) = O _V (G). Conversely, assume that t _V (G) = O _V (G). If there exists a vertex u with neighbors v and w, then V - {u} is a total dominating set of G. So that t _V (G) ≤ O _V (G) which is a contradiction. Therefore, every vertex of G has unique neighbor.□

Definition 3.20. Let G = (V, E) be a vague graph and S be a set of vertices.

A vertex v is said to be a vague private neighbor of u ∈ S with respect to S, if N [v] ∩ S = {u}. Furthermore, we define vague private neighborhood of u ∈ S with respect to S, by PN [u, S] = {v : N [v] ∩ S = {u}}. In other words PN [u, S] = N [u] - N [S - {u}].

A vertex u in S ⊆ V is said to be vague redundant vertex if PN [u, S] =∅. Equivalently u is redundant in S if N [u] ⊆ N [S - {u}]. Otherwise u is said to be fuzzy irredundant vertex.

A set S ⊆ V is said to be vague irredundant set if PN [u, S]≠ ∅, for every vertex in S.

A vague irredundant set S is maximal vague irredundant set if for every vertex v ∈ V - S, the set S ∪ {v} is not vague irredundant set, which means that there is at least one vertex w ∈ S ∪ {u} which does not have any private neighbor.

Maximum cardinality among all maximal vague irredundant set is called upper vague irredundance number and is denoted by IR _V (G).

Minimum cardinality among all maximal vague irredundant set is called lower vague irredundance number and is denoted by ir _V (G).

Example 3.21. Consider a vague graph G = (V, E) such that V = {u ₁, u ₂, u ₃, u ₄, u ₅} and E = {(u ₁, u ₂) , (u ₂, u ₃) , (u ₃, u ₄) , (u ₄, u ₁) , (u ₁, u ₆) , (u ₄, u ₆) , (u ₅, u ₆) , (u ₂, u ₅) , (u ₃, u ₅)}.

In Fig. 3, S ₁ = {u ₁, u ₄, u ₆}, S ₂ = {u ₂, u ₃, u ₅} and S ₃ = {u ₁, u ₂} are three vague irredundant sets, PN [u ₁, S ₁] = {u ₂}, PN [u ₄, S ₁] = {u ₃} and PN [u ₆, S ₁] = {u ₅}. {u ₅, u ₆} has minimum cardinality among all maximal vague irredundant sets and ir _V (G) =0.7. {u ₂, u ₃, u ₅} has maximum cardinality among all maximal vague irredundant sets and IR _V (G) =1.25.

Theorem 3.22. For any vague graph G = (V, E) with order O (G) and minimum degree δ (G), ir _V (G) ≤ O (G) - δ (G).

Proof. Let S be an irredundant set in a vague graph G = (V, E). Let v be a vertex in S which is a strong neighbor to some vertices in S whose some of the cardinality is |k|. Since the neighborhood degree of v is at least δ (G), v must be strong neighbor to at least some vertices in V - S whose sum of cardinality is δ (G) - |k|. Here δ (G) - |k| ≤ |V - S|. If |k|=0, then δ (G) ≤ |V - S|. That is δ (G) ≤ O (G) - ir _V (G) or ir _V (G) ≤ O (G) - δ (G). If |k|>0, then each neighbor of v in S must be distinct and have a private neighbor V - S. Hence |V - S| ≥ (δ (G) - |k|) + |k| = δ (G). Thus, ir _V (G) ≤ O (G) - δ (G).□

Remark 3.23. Every maximal vague independent set in a vague graph G is a maximal vague irredundant set. That is ir _V (G) ≤ i _V (G) ≤ d _V (G) ≤ IR _V (G).

Theorem 3.24. In any vague graph of order O (G) and minimum neighborhood degree δ (G), ir _V (G) + IR _V (G) ≤2 (O (G) - δ (G)). The equality holds if and only if (O (G) - δ (G)) divides O (G).

Proof. From Theorem 3.22 and Remark 3.23, we have ${ir}_{V} (G) \leq {IR}_{V} (G) \leq O (G) - δ (G) . (1)$

Thus ir _V (G) + IR _V (G) ≤2 (O (G) - δ (G)). If (O(G) - δ (G)) divides O (G), then we have a complete multipartite vague graph each of whose defining independent set of size is (O (G) - δ (G)). Hence, i _V (G) = IR _V (G) = (O (G) - δ (G)). It follows ir _V (G) + IR _V (G) =2 (O (G) - δ (G)). Conversely, if ir _V (G) + IR _V (G) =2 (O (G) - δ (G)), then by (1), i _V (G) = IR _V (G) = (O (G) - δ (G)). It follows that every vertex of G lies in a maximal independent set of size (O (G) - δ (G)). Since, δ (G) is the minimum neighborhood degree, every vertex in such a maximal independent set is a strong neighbor to every vertex outside the set. It follows that the vertex set V can partitioned into maximal independent set of size (O (G) - δ (G)), and hence (O (G) - δ (G)) divides O (G). It follows that the graph G is a complete multipartite vague graph.□

4 Applications of domination in vague graphs

These days, we see that graph models have many applications in different sciences such as computer sciences, topology, operation research, biological and social sciences. If we consider group behavior, it is observed that in a social group some people can influence thinking of others and it can happen when there is a strong relation between them. Now let us to consider a vague graph of a social group in Fig. 4.

The nodes are depicting the degree of power of a person belongs to a set of social group. The degree of power of a person is defined in terms of its true membership and false membership. Degree of true membership can be interpreted as how much power a person posses and false membership can be interpreted as how much power a person losses, A has 20% power within the social group but he losses 40% power in the same group. In this example, {A, B}, {E, F}, {B, C} and {C, D} are strong edges. So, we can say there is a strong relation between A and B. It is true for E, F and B, C too. Hence we see that B dominates A, E dominates F and C dominates B. It is clear that {a, c, e}, {a, c, e, d} and {a, c, d, f} are dominating sets. Therefore, domination can help us to find people who have strong relation in a social group. Domination can be applied in other areas which we have listed below.

4.1 School bus routing

Most school in the country provide school buses for transporting children to and from school most also operate under certain rules, one of which usually states that no child shall have to walk farther than, say one quarter km to a bus pick up point. Thus, they must construct a route for each bus that gets within one quarter km of every child in its assigned area. No bus ride can take more than some specified number of minutes, and limits on the number of children that a bus can carry at any one time. Let us say that the following figure represents a street map of part of a city, where each edge represents one pick up block. The school is located at the large vertex. Let us assume that the school has decided that no child shall have to walk more than two blocks in order to be picked up by a school bus. Construct a route for a school bus that leaves the school, gets within two blocks of every child and returns to the school.

4.2 Modeling Biological Networks

Using graph theory as a modeling tool in biological networks allows the utilization of the most graphical invariants in such a way that it is possible to identify secondary RNA (Ribonucleic acid) motifs numerically. Those graphical invariants are variations of the domination number of a graph. The results of the research carried out in show that the variations of the domination number can be used for correctly distinguishing among the trees that represent native structures and those that are not likely candidates to represent RNA.

4.3 Modeling social networks

Dominating sets can be used in modeling social networks and studying the dynamics of relations among numerous individuals in different domains. A social network is a social structure made of individuals (or groups of individuals), which are connected by one or more specific types of interdependency. The choice of initial sets of target individuals is an important problem in the theory of social networks. In the work of Kelleher and Cozzens, social networks are modeled in terms of graph theory and it was shown that some of these sets can be found by using the properties of dominating sets in graphs.

4.4 Coding theory

The concept of domination is also applied in coding theory as discussed by Kalbfleisch, Stanton and Horton and Cockayne and Hedetniemi. If one defines a graph, the vertices of which are the n-dimensional vectors with coordinates chosen from {1, . . . , p} , p > 1, and two vertices are adjacent if they differ in one coordinate, then the sets of vectors which are (n, p)- covering sets, single error correcting codes, or perfect covering sets are all dominating sets of the graph with determined additional properties.

5 Conclusion

Fuzzy graph theory has numerous applications in modern sciences and technology, especially in the fields of operations research, neural networks, artificial intelligence and decision making. At present, domination is considered to be one of the fundamental concepts in graph theory and its various applications to biological networks, distributed computing and social networks. In this paper, we introduced the concepts of cardinality, dominating set, independent set, total dominating number and independent dominating number of vague graphs. The notion of a irredundance number of a vague graph is discussed also.

Acknowledgments

The authors are thankful to all the reviewers, Associate editor, Editor-in-Chief of the journal for their important suggestions to improve the presentation of the paper. This work was supported by the research grant (Vague Fuzzy Graphs) of the Islamic Azad University, Central Tehran Branch, Tehran, Iran

References

Akram

Gani

Borumand Saeid

2014

Vague hypergraphs

Journal of Intelligent and Fuzzy Systems 26 647 653

Akram

Wenjuan Chen

Shum

2013

some properties of vague graphs

Southeast Asian Bulletin of Mathematics 37 307 324

Debnath

2013

Domination in interval-valued fuzzy graphs

Annals of Fuzzy Mathematics and Informatics 6 2 363 370

Gau

Buehrer

1993

Vague sets

IEEE Transactions on Systems Man and Cybernetics 23 2 610 614

Kauffman

1973

Introduction a la theorie des sous-emsembles flous

Masson et Cie 1

Pal

Rashmanlou

2013

Irregular interval-valued fuzzy graphs

Annals of Pure and Applied Mathematics 3 1 56 66

Parvathi

Thamizhendhi

2010

Domination in intuitionistic fuzzy graphs

Fourteenth Int Conf on IFSs, Sofia 16 2 39 49

Ramakrishna

2009

Vague graphs

International Journal of Computational Cognition 7 51 58

Rosenfeld

1975

Fuzzy graphs, Fuzzy Sets and their Applications

Zadeh

Shimura

77 95

Academic Press

New York

10.

Rashmanlou

Pal

2013

Antipodal interval-valued fuzzy graphs

International Journal of Applications of Fuzzy Sets and Artificial Intelligence 3 107 130

11.

Rashmanlou

Pal

2013

Balanced interval-valued fuzzy graph

Journal of Physical Sciences 17 43 57

12.

Rashmanlou

Jun

2013

Complete interval-valued fuzzy graphs

Annals of Fuzzy Mathematics and Informatics 6 3 677 687

13.

Rashmanlou

Samanta

Pal

Borzooei

2015

A study on bipolar fuzzy graphs

Journal of Intelligent and Fuzzy Systems 28 571 580

14.

Samanta

Pal

2011

Fuzzy tolerance graphs

International Journal Latest Trend Math 1 2 57 67

15.

Samanta

Pal

2011

Fuzzy threshold graphs

CiiT International Journal of Fuzzy Systems 3 12 360 364

16.

Samanta

Pal

2014

New concepts of fuzzy planar graph

International Journal of Advanced Research in Artificial Intelligence 3 1 52 59

17.

Samanta

Pal

2013

Fuzzy k-competition graphs and pcompetition fuzzy graphs

Fuzzy Engineering and Information 5 2 191 204

18.

Samanta

Pal

2012

Irregular bipolar fuzzy graphs

International Journal of Applications of Fuzzy Sets 2 91 102

19.

Somasundaram

1998

Domination in fuzzy graphs-I

Pattern Recognition Letters 19 787 791

20.

Zadeh

1965

Fuzzy sets

Information and Control 8 338 353

21.

Zadeh

1971

Similarity relations and fuzzy ordering

Information Sciences 3 177 200

22.

Zadeh

2008

Is there a need for fuzzy logic?

Information Sciences 178 2751 2779