Strong incidence domination in fuzzy incidence graphs

1 Introduction

A graph is one of the most effective and explicit ways to represent information and relation between various entities. The vertex set V of the graph represents elements and, the edge set E⊆V × V represents the relation between them. A weighted graph depicts relational strength between the vertices. Domination in graphs is one of the most significant areas of research due of its application in various fields. It was in the 1850s that the idea of domination originated through the chessboard domination problem. The study of domination was initiated in 1962, by Ore [21] and Berge[5] and, Hedetniemi and Cockayne[6, 13] further studied it. The vague or ambiguous nature of the elements and their relationship instigated the concept of Fuzzy graphs (FGs). Rosenfeld[25] introduced the study on FGs and the fuzzy analog of graph concepts like cycle, paths, trees, connectedness, etc, in 1975. FG models are beneficial than graph models because FG models acknowledge the vagueness and uncertainty in the entities considered in the modeling. Somasundaram and Somasundaram[27] introduced the idea of FG domination using effective arcs. Nagoor Gani and Chandrashekharan[18] proposed the notion of domination in FGs using strong arcs. Manjusha et al. [15] examined domination number in FG using the weight of strong arcs. Many authors including Parvathi and Thamizhendi[23], Karunambigai[14], Debnath[11], Borzooei and Rashmanlou[7] have also contributed towards the domination in several types of FGs like intuitionistic FG, bipolar FG, interval-valued FG and vague graphs respectively. Sahoo et al. [26] studied covering and paired domination in intuitionistic fuzzy graphs. Bera et al. [4] introduced a new concept of domination in m-polar interval valued fuzzy graphs. The recent developments in fuzzy graph theory are in [22]. The FG model proves to be an inadequate model to represent the data when the elements of set V have a certain influence over the elements of set V × V. For example, suppose the vertices of a graph are represented as cities and edges as the roads connecting them. The elements of the form (c, cd) represent the ramp from city c to road cd. If the population is taken as vertex weight, and extent of traffic as edge weight, it results in a FG model with an additional property of vertices having some influence over the edges. This is because, more population in a city result in more ramps from the city to the roads. This problem encouraged the researchers to introduce the notion of Fuzzy Incidence Graph (FIG). Dinesh[12] defined the term FIG and established several of its properties. Mordeson et al. [16, 17] presented the connectivity concepts, notion of fuzzy end nodes and vertex connectivity and edge connectivity in FIGs. Akram et al. [2, 3] explored the concept of neutrosophic incidence graphs and also the application of bipolar neutrosophic sets to incidence graphs. Nazeer et al.[19, 20] developed the idea of FIG domination using effective pairs and have also defined strong domination in FIG and their join. Rao et al.[24] explored domination in vague incidence graphs. Recently, Afsharmanesh et al. [1] introduced domination based on valid edges in FIGs. Some significant developments in the vertex domination in Graphs, FGs and FIGs is illustrated in Figure 1.

OPEN IN VIEWER

Fig. 1

Vertex dominations in graphs, FGs and FIGs.

This article intends to introduce a new concept of strong incidence domination (SID) in FIGs. The motivation for studying the notion of strong incidence domination is that, the domination parameters introduced by other authors is defined using effective pairs and incidence valid edges. When a fuzzy incidence graph is used to model a real-world problem it is not always possible to obtain a fuzzy incidence graph with incidence valid edges or effective pairs. But the concept of strong incidence domination defined in this study can always be used in any fuzzy incidence graphs, since the pairs can be classified into strong and non strong pairs in any FIG. Also, unlike other domination parameters which are defined using the weight of vertices, strong incidence domination is defined using the weight of strong pairs. Hence, the least value is obtained using the strong incidence domination.

The article is organised as follows: Section 2 elucidates some basic definition in FGs and FIGs. Section 3 introduces the concept of SIDS and SIDN on FIGs. Degree of a vertex using strong pairs is defined. A characterisation for the domination number to be half of the order of FIG is proved. Minimal strong incidence dominating sets (MSIDS) and bounds for the SIDN is also provided in this section. Some properties of SIDS and SIDN of some FIGs is examined. Section 4 discusses a social application of the SIDN. Section 5 is a comparative study of different types of dominations in FIG.

Throughout the paper, ∧ and ∨ represents minimum and maximum operators respectively. The following definitions are from [12, 27].

An incidence graph (IG), is a triple G = (V, E, I) where V is non-empty, E ⊆ V × V and I ⊆ V × E.

Elements in I are of the form (b, cd) where b ∈ V and e = cd ∈ E, and are called incidence pairs or simply pairs.

The edges ab and cd will be considered adjacent only if (a, ab) , (b, ba) , (c, cd) and (d, dc) are in I.

An incidence subgraph H of an IG, G is such that all its vertices, edges and pairs are in G.

Let G be an IG, an incidence walk from c′ to d′ where c′, d′ ∈ V ∪ E is a sequence of elements of V, E and I starting at c′ and ending at d′. An incidence walk is called incidence trail if the pairs in it are distinct. Similarly incidence walk is called incidence path if the vertices in it are distinct. A connected IG is an IG in which all pairs of vertices are joined by a path. A maximally connected incidence subgraph of an IG is called a component of the IG.

Let φ, ρ and ζ be fuzzy subsets of V, E ⊆ V × V and V × E respectively. If ρ (cd) ≤ φ (c) ∧ φ (d) for all c, d ∈ V, then G = ( V , φ , ρ ) is called a Fuzzy Graph (FG). Also, ζ is called fuzzy incidence of G , if ζ (v, e) ≤ φ (v) ∧ ρ (e) for all v ∈ V and e ∈ E and G ˜ = ( φ , ρ , ζ ) is called Fuzzy Incidence Graph (FIG) of G .

Now, φ^*, ρ^* and ζ^* are supports of φ, ρ and ζ respectively defined as follows: φ^* = {c ∈ V : φ (c) >0}, ρ^* = {e ∈ E : ρ (e) >0}, and ζ^* = {(c, cd) ∈ I : ζ (c, cd) >0}. A FIG is trivial if |φ^*|=1.

Here, G = ( V , φ , ρ ) is called the underlying FG of FIG, G ˜ . Then G * = ( V , φ * , ρ * ) is the underlying crisp graph of the FG, G . Next, p = ∑_c∈Vφ (c) and q = ∑_(c,d)∈V×Vρ (cd) are called the order and size of the FG, G respectively. Similarly, O = ∑_{c≠d,(c,cd)∈ζ^*}ζ (c, cd) and S = ∑_e∈ρ^*ρ (e) are the order and size of FIG, G ˜ respectively. A FG is called bipartite if V = V₁ ∪ V₂ where V₁ and V₂ are partitions of V and ρ (cd) =0 if c, d ∈ V₁ or c, d ∈ V₂.

Let cd ∈ ρ^*, and (c, cd) , (d, dc) ∈ ζ^*, then cd is an edge of the FIG G ˜ . Elements of the form (c, cd) are called pairs of G ˜ . Vertices c and d of the FIG are connected if they are joined by a path. The FIG is said to be connected if every pair of vertices is joined by a path. A FIG, H ˜ = ( τ , υ , Ω ) is a fuzzy incidence subgraph of the FIG, G ˜ if τ ⊆ φ, υ ⊆ ρ, and Ω ⊆ ζ. If τ = φ, then H ˜ is called a fuzzy incidence spanning subgraph of G ˜ . Also, H ˜ is a subgraph of G ˜ if τ = φ, υ = ρ, and Ω = ζ for the elements in τ^*, υ^* and Ω^* respectively.

A FIG, G ˜ is fuzzy incidence complete graph (CFIG) if ζ (c, cd) =  ∧ {φ (c) , ρ (cd)} for all (c, cd) ∈ V × E. The pairs (c, cd) such that ζ (c, cd) =  ∧ {φ (c) , ρ (cd)} are called effective pairs.

Let G = ( V , φ , ρ ) be a FG. The strength of a path in G is the minimum ρ values of edges in it. The maximum of the strengths of all paths between c and d is called the strength of connectedness between c and d denoted as ρ^∞ (c, d). Similarly, let G ˜ = ( φ , ρ , ζ ) be a FIG. The incidence strength of a fuzzy incidence path is the minimum ζ values of the pairs in it. The incidence strength of a path from b to cd of greatest incidence strength is denoted as ζ ∞ ( b , cd ) or ICONN G ˜ ( b , cd ) .

A FIG, G ˜ = ( φ , ρ , ζ ) is a forest if (φ^*, ρ^*, ζ^*) is a forest and a tree if it is also connected.

If the FIG, G ˜ = ( φ , ρ , ζ ) has a fuzzy incidence spanning subgraph F ˜ = ( φ , ν , Ω ) which is a forest and ζ (c, cd) < Ω^∞ (c, cd) for (c, cd) ∈ ζ^* \ Ω^*, then G ˜ is called a fuzzy incidence forest (FIF) and a fuzzy incidence tree (FIT), if it is also connected. A FIG, G ˜ = ( φ , ρ , ζ ) is a cycle if (φ^*, ρ^*, ζ^*) is a cycle. If in addition, G ˜ has the property that there exists no unique cd ∈ ρ^* with the least ρ value, then it is called a fuzzy cycle (FC). A fuzzy incidence cycle (FIC) is FIG, G ˜ = ( φ , ρ , ζ ) which is a fuzzy cycle with the property that there is no unique (c, cd) ∈ ζ^* with the least ζ value.

Let G ˜ = ( φ , ρ , ζ ) be a FIG and ζ^′∞ (b, cd) is the greatest incidence strength among the incidence strength of all paths from b to cd when (b, cd) is deleted from G ˜ . If ζ^′∞ (c, cd) < ζ^∞ (c, cd) for some (c, cd) in G ˜ where ζ′ = ζ_{(V×E)\{(a,ab)}}, then the pair (a, ab) is called incidence cutpair of G ˜ .

The edge cd is called a bridge if ρ^′∞ (a, b) < ρ^∞ (a, b) for some a, b ∈ φ^* and ρ′ = ρ_E\cd. Let b ∈ V and E′ = E \ K where K is set of edges with b as end vertex. If ρ^′∞ (c, d) < ρ^∞ (c, d) for some c, d ∈ φ^* and c ≠ b ≠ d where ρ′ = ρ_E′, then b is called a cutvertex of G ˜ , and b is a fuzzy incidence cutvertex (FICV) if ζ^′∞ (c, cd) < ζ^∞ (c, cd) for some (c, cd) in V × E′ and c ≠ b ≠ d where ζ′ = ζ_(V×E′).

An edge cd in a FG is α- strong if ρ (cd) > ρ^′∞ (c, d), β- strong if ρ (cd) = ρ^′∞ (c, d) and δ edge if ρ (cd) < ρ^′∞ (c, d). An edge is strong if it is either α- strong or β- strong. Similarly, in FIG, G ˜ , a pair (c, cd) is α- strong if ζ (c, cd) > ζ^′∞ (c, cd), β- strong if ζ (c, cd) = ζ^′∞ (c, cd) and, δ- pair if ζ (c, cd) < ζ^′∞ (c, cd). Also, (c, cd) is a δ^* pair if ζ (c, cd) is greater than the least ζ value of the elements in ζ^*. A pair is strong if it is either α or β strong. If (c, cd) is strong, then c and cd are strong fuzzy incidence neighbors. A fuzzy incidence path is strong incidence path (SIP), if every pair in it is strong. A FIG, G ˜ is strong FIG (SFIG), if every pair in G ˜ is strong. A vertex c is called fuzzy incidence end vertex (FIEV) if it has at most one strong neighbor. Similarly, if an edge has at most one strong neighbor then it is called fuzzy incidence end edge (FIEE). Also, FIEV and FIEE together are called fuzzy incidence end nodes (FIEN).

The strong domination in FG, G is defined as follows. A vertex c is a strong neighbor of vertex d if edge cd is strong. A vertex dominates itself and its strong neighbors. A set D ⊆ V is a strong dominating set (SDS), if each vertex in V \ D is dominated by some vertex in D. Then, W (D) = ∑_c∈Dρ (cd) is called the weight of D where ρ (cd) is the minimum weight of strong edges incident at c. The strong domination number (SDN), γ _S , is the minimum of weights of SDSs in G and a dominating set with weight γ _S is called minimum SDS.

3 Strong incidence domination in fuzzy incidence graph

A new domination parameter in a fuzzy incidence graph (FIG) using the strong pairs is discussed in this section. The definition of SIDN is obtained using weight of strong pairs. Also, bounds for the SIDN are examined. The MSIDS is considered and the result that each vertex in a FIG with non-trivial components will dominate at least one vertex other than itself is proved. A method to construct a spanning subgraph of the FIG which is a tree with only strong pairs is discussed. Some properties of SIDS and SIDN of fuzzy incidence path, FIC, FIT, CFIG and complete bipartite FIG are also explored subsequently. This section begins with some definitions:

In all the following definitions let G ˜ = ( φ , ρ , ζ ) be a FIG.

Definition 3.1. A vertex d is called the strong incidence neighbor (SIN), of vertex c if both the pairs (c, cd) and (d, cd) are strong.

Definition 3.2. The set of all vertices that are SINs of c is called the strong incidence neighborhood of c, denoted by N _IS  (c). N _IS  [c] is the closed strong incidence neighborhood of c, N _IS  [c] = N _IS  (c) ∪ {c}.

Definition 3.3. The strong pair degree d _sp  (c) of a vertex c ∈ V is defined as, d sp ( c ) = ∑ d ∈ N IS ( c ) ζ ( c , cd ) The minimum and maximum strong pair degree are defined as δ _sp  = ∧ {d _sp  (c) : c ∈ V} and Δ _sp  = ∨ {d _sp  (c) : c ∈ V} respectively.

Definition 3.4. The strong incidence neighborhood degree d _ISN  (c) of a vertex c is defined as, d ISN ( c ) = ∑ d ∈ N IS ( c ) φ ( d ) The minimum and maximum strong incidence neighborhood degree are defined as δ _ISN  = ∧ {d _ISN  (c) : c ∈ V} and Δ _ISN  = ∨ {d _ISN  (c) : c ∈ V} respectively.

Definition 3.5. A vertex c in the FIG, G ˜ dominates vertex d if either c = d or d is a SIN of c. Hence a vertex c dominates vertices in N _IS  [c]. Note that, if a vertex c dominates a vertex d, it implies that d dominates c. A vertex c is isolated if N _IS  (c) = φ. For a set S ⊆ V, c ∈ S is called an isolated vertex of S if N _IS  (c) ⊆ V \ S.

Definition 3.6. A strong incidence dominating set (SIDS), is a set S ˜ ⊆ V in G ˜ such that, for any d ∈ V - S ˜ , ∃ some c ∈ S ˜ such that, c is a SIN of d.

Definition 3.7. The weight W ( S ˜ ) of a SIDS, S ˜ is defined as W ( S ˜ ) = ∑ c ∈ S ˜ ζ ( c , cd ) where ζ (c, cd) is minimum weight of strong pairs at c and d ∈ N _IS  (c).

Definition 3.8. The minimum weight of the SIDSs in the FIG, G ˜ is called the strong incidence domination number (SIDN) of G ˜ , denoted by γ IS ( G ˜ ) or γ _IS  . The SIDS with minimum weight is called a minimum SIDS.

Example 3.9. Consider the FIG in the Figure 2. Here all pairs are strong except (z, zx) and (x, xw). The sets {w, y} , {x, z} , {x, w} and {z, y} are SIDS with two elements with weights 0.3, 0.4, 0.4 and 0.3 respectively. Hence the SIDN, γ _IS  = 0.3 and the minimum SIDS are {w, y} and {z, y} .

OPEN IN VIEWER

Fig. 2

Illustration of SIDN in FIG.

Remark 3.10. For FIG with trivial components γ _IS  = 0, and the minimum SIDS is the vertex set V.

Remark 3.11. Since ζ (x, e) ≤ φ (x) ∧ ρ (e) forall x ∈ V and e ∈ E and each vertex in the dominating set contributes the weight of only one strong pair to the domination number, it follows that γ _IS  ≤ p.

Proposition 3.12. If G ˜ = ( φ , ρ , ζ ) is a FIG without isolates and γ _IS  = ∧ {ζ (u, uv) , v ∈ V} for some vertex u, then |N _IS  (u) | = n - 1 where |φ^*| = n.

Proof. Since γ _IS  = ∧ {ζ (u, uv) , v ∈ V}, this implies that u dominates all vertices in G ˜ . ∴|N _IS  (u) | = n - 1.

The converse of Proposition 3.12 is not always true as in Example 3.13.

Example 3.13. Consider the FIG in Figure 3. Note that, here every pair is strong. Hence, |N _IS  (v) |=2 = n - 1 but γ _IS  = 0.1≠ ∧ {ζ (v, xv) : x ∈ V}. The minimum SIDS is {u, w} .

OPEN IN VIEWER

Fig. 3

FIG with γ _IS  = 0.1.

Remark 3.14. Since the contribution of a vertex in the SIDS to the SIDN is the weight of only one strong pair incident at it, it follows that, γ _IS  ≤ O/2, where O is the order of the FIG.

The following proposition gives a sufficient condition for a pair to be strong in a FIG.

Proposition 3.15. G ˜ = ( φ , ρ , ζ ) is a FIG and cd ∈ ρ^*. Then (c, cd) is a strong pair if ζ (d, cd) ≤ ζ (c, cd).

Proof. The pair (c, cd) is a strong pair if ICONN G ˜ \ ( c , cd ) ( c , cd ) ≤ ζ ( c , cd ) . Any incidence path from c to cd in G ˜ \ ( c , cd ) consists of the pair (d, cd). Therefore, ICONN G ˜ \ ( c , cd ) ( c , cd ) ≤ ζ ( d , cd ) ≤ ζ ( c , cd ) which implies that (c, cd) is strong.

Example 3.16 illustrates that the converse of Proposition 3.15 is not true.

Example 3.16. For the FIG given in Figure 4, the pair (v, vw) is a strong pair(β-pair) but ζ (w, vw) > ζ (v, vw).

OPEN IN VIEWER

Fig. 4

FIG with strong pairs.

Remark 3.17. Consider FIG, G ˜ = ( φ , ρ , ζ ) . Suppose corresponding to each edge cd ∈ ρ^*, the pairs (c, cd) and (d, dc) have same weight, then by Proposition 3.15, both (c, cd) and (d, dc) will be strong pairs. Also, all effective pairs are pairs of this form. But the converse is not true. As an example, the pairs (z, zw) and (w, wz) in Figure 2 have same weight but they are not effective pairs since ζ (z, zw) ≠ φ (z) ∧ ρ (zw) and ζ (w, zw) ≠ φ (w) ∧ ρ (zw).

Theorem 3.18. Let G ˜ = ( φ , ρ , ζ ) be FIG, γ IS = O 2 iff |N _IS  (u) |≤1 ∀u ∈ φ^* and G ˜ is a FIG such that the pairs (x, xy) and (y, xy) associated with each edge xy ∈ ρ^* have equal weight.

Proof. Suppose that G ˜ = ( φ , ρ , ζ ) is a FIG such that |N _IS  (u) |≤1 ∀u ∈ φ^* and ζ (x, xy) = ζ (y, xy) for the pairs associated with each edge xy. Then all isolated vertices will be in the SIDS. Also if u and v are SINs then only one among them will belong to the SIDS. Therefore, clearly γ IS = O 2 .

Conversely, suppose that γ IS = O 2 . If possible let |N _IS  (u) |>1 for some u ∈ V.

Since the weight of only one pair incident at the vertex in the SIDS contributes to the SIDN, in this case γ IS < O 2 , a contradiction. Therefore |N _IS  (u) |≤1 ∀u ∈ φ^*.

Now, assume that G ˜ is FIG such that the weight of the pairs corresponding to each edge is not equal. Then there exists at least one xy ∈ ρ^* such that, ζ (x, xy) < ζ (y, xy). Hence, only ζ (x, xy) will be contributing to the SIDN. So γ IS < O 2 , a contradiction. Therefore, G ˜ is a FIG with ζ (x, xy) = ζ (y, xy) for the pairs associated with each edge xy.

Next, MSIDS of a FIG is defined and some of its properties are established.

Definition 3.19. A SIDS, S ˜ is a minimal strong incidence dominating set (MSIDS) if no proper subset of it is a SIDS.

Example 3.20. Consider the FIG in Figure 2. The sets {w, x} , {w, y} , {z, x} , and {z, y} are MSIDS since no proper subsets of these sets are SIDSs.

Theorem 3.21. A SIDS, S ˜ in G ˜ is minimal SIDS iff for any s ∈ S ˜ , one the following conditions hold:

s is an isolated vertex of S ˜ .

Proof. Suppose that S ˜ is a MSIDS. Then for any s ∈ S ˜ , S ˜ \ s is not a SIDS. This implies that, there exists some u ∈ V \ { S ˜ \ s } which has no SIN in S ˜ \ s . If u = s, then s is isolated in S ˜ , and so (1) holds. If u ≠ s, since u has no SIN in S ˜ \ s , then s is the SIN of u in S ˜ i.e, N IS ( u ) ∩ S ˜ = { s } . Hence (2) holds.

Conversely suppose S ˜ is a SIDS, such that, one of the given two conditions hold for any s ∈ S ˜ . If S ˜ is not MSIDS then, there exists a s ∈ S ˜ such that S ˜ \ s is a SIDS. Therefore, s is dominated by a vertex in S ˜ \ s , which implies s is not isolated in S ˜ i.e, (1) does not hold. Also, since S ˜ \ s is a SIDS for each u ∈ V \ S ˜ there exists a SIN of u in S ˜ \ s which means N IS ( u ) ∩ S ˜ contains vertices other than s. Hence (2) does not hold. This contradicts our assumption, hence the result.

Theorem 3.22. If G ˜ is a FIG without isolated vertices and S ˜ is a minimal SIDS in G ˜ , then V \ S ˜ is a SIDS.

Proof. Let S ˜ be a MSIDS. If V \ S ˜ is not a SIDS, then there exists some vertex s ∈ S ˜ , that has no SIN in V \ S ˜ . Since there are no isolates, s must have a SIN in S ˜ \ { s } . Therefore, S ˜ \ { s } is also a SIDS which is a contradiction to the fact that S ˜ is minimal. Hence V \ S ˜ is a SIDS.

Next, bounds for the SIDN are obtained in Theorems 3.23 and 3.25.

Theorem 3.23. For a FIG, G ˜ = ( φ , ρ , ζ ) with at least one non-trivial component, ∧ { ζ ( u , uv ) | ( u , uv ) ∈ ζ * } ≤ γ IS ≤ p - Δ ISN

Proof. Suppose that G ˜ is a connected non-trivial FIG and the minimum SIDS consists of a single vertex say x, where x ∈ V. This implies that the vertex x dominates every other vertex in the FIG. In that case, SIDN, γ _IS  = ∧ {ζ (x, xy) |y ∈ N _IS  (x)}. Suppose that the pair (x, xz) has the least ζ value among all the pairs. Then γ _IS  = ζ (x, xz). Therefore, γ _IS  ≥ ∧ {ζ (u, uv) : (u, uv) ∈ ζ^*}. If G ˜ is disconnected, where at least one component is non-trivial γ _IS  ≥ ∧ {ζ (u, uv) : (u, uv) ∈ ζ^*}. Hence, the first inequality is obtained.

For the second inequality, let u be a vertex such that d _ISN  (u) = Δ _ISN . Then V \ N _IS  (u) is a SIDS. Therefore, γ _IS  ≤ W (V \ N _IS  (u)) ≤ p - Δ _ISN .

Remark 3.24. The inequalities in Theorem 3.23 are sharp for complete fuzzy incidence graphs.

Theorem 3.25. If G ˜ = ( φ , ρ , ζ ) is a FIG, then γ IS ≤ O - Δ sp

Proof. Let u ∈ V be such that d _sp  (u) = Δ _sp and N _IS  (u) = {v₁, v₂, . . . , v _m }. Also assume that ζ (u, uv₁) = ∧ {ζ (u, uv₁) , ζ (u, uv₂) . . . ζ (u, uv _m )}. Let S ˜ be a minimum SIDS of G ˜ with k vertices. Then consider the following two cases:

Case1: u ∈ S ˜

If u ∈ S ˜ , then not all SINs of u are in S ˜ . Because if all neighbors of u are in S ˜ , then S ˜ \ { u } is also a SIDS with weight less than that of S ˜ , which is not possible. Now let S′ be the set of SINs of u which are not in S ˜ . Let γ IS = ζ ( u , uv 1 ) + w 2 + w 3 + . . . + w k where w _i , 2 ≤ i ≤ k represent the minimum weight of pairs incident at each of the remaining k - 1 vertices in S ˜ . Also, d sp ( u ) = ζ ( u , uv 1 ) + ζ ( u , uv 2 ) + . . . + ζ ( u , uv m )

Then O = ζ ( u , uv 1 ) + ζ ( u , uv 2 ) + . . . + ζ ( u , uv m ) + w 2 + w 3 + . . . + w k + W where W is the sum of weight of the remaining pairs in the FIG.

Suppose that γ _IS  > O - Δ _sp . Then we will get ζ ( u , uv 1 ) + w 2 + w 3 + . . . + w k > ζ ( u , uv 1 ) + ζ ( u , uv 2 ) + . . . + ζ ( u , uv m ) + w 2 + w 3 + . . . + w k + W - ( ζ ( u , uv 1 ) + ζ ( u , uv 2 ) + . . . + ζ ( u , uv m ) ) impliesζ (u, uv₁) > W

Since the sum of weight of the pairs in S′ is included in W, the sum of weight of pairs in S′ is less than ζ (u, uv₁). Then, consider the set ( S ˜ \ { u } ) ∪ S ′ which is a SIDS with weight less than that of S ˜ , a contradiction.

Case 2: u ∉ S ˜ γ IS = w 1 + w 2 + w 3 + . . . + w k where w _i , 1 ≤ i ≤ k are the minimum weights of pairs incident at each of the k vertices in S ˜ . And, d sp ( u ) = ζ ( u , uv 1 ) + ζ ( u , uv 2 ) + . . . + ζ ( u , uv m ) Then O = ζ ( u , uv 1 ) + ζ ( u , uv 2 ) + . . . + ζ ( u , uv m ) + w 1 + w 2 + w 3 + . . . + w k + W Suppose that γ _IS  > O - Δ _sp ⇒ w 1 + w 2 + w 3 + . . . + w k > ζ ( u , uv 1 ) + ζ ( u , uv 2 ) + . . . + ζ ( u , uv m ) + w 1 + w 2 + w 3 + . . . + w k + W - ( ζ ( u , uv 1 ) + ζ ( u , uv 2 ) + . . . + ζ ( u , uv m ) ) impliesW < 0, a contradiction.

Hence the result.

Example 3.26 gives an example of a FIG for which the bound in Theorem 3.25 is sharp.

Example 3.26. For the FIG in Figure 5, γ IS = 0.2 = O - Δ sp ( G ˜ ) .

OPEN IN VIEWER

Fig. 5

FIG with γ _IS  = O - Δ _sp .

Next, the result that, in a FIG with non-trivial components each vertex is dominated by at least one distinct vertex is proved in Theorem 3.28.

Theorem 3.27. [16] G ˜ is a connected FIG, then from any element u ∈ φ^* to any element vw ∈ ρ^* in G ˜ , there exists a SIP.

Theorem 3.28. Let G ˜ = ( φ , ρ , ζ ) is a FIG with non-trivial components then, every vertex in G ˜ is dominated by at least one distinct vertex.

Proof. Let G ˜ = ( φ , ρ , ζ ) be a connected FIG with |φ^*|>1 and let u be an arbitrary vertex in G ˜ . Since |φ^*|>1, there exists at least one edge say uv incident at u. If possible assume that u is not dominated by any vertex in G ˜ . Then corresponding to each edge uw at u either (u, uw) or (w, uw) will be a δ-pair.

Case 1: There are no edges in G ˜ , other than the edges incident at u.

This clearly implies that all the pairs are strong, a contradiction.

Case 2: There are edges in G ˜ , other than the edges incident at u.

Let xy be one such edge. Consider u and the edge xy. There will not be any SIP from u to xy, which is not possible by Theorem 3.27. Therefore, every vertex in G ˜ is dominated by at least one vertex.

In the case of a disconnected FIG, each component is a connected FIG. Therefore each vertex will be dominated by a vertex in the same component and can be proved in a similar way as done in the case of connected FIG.

Remark 3.29. In Theorem 3.30, it is established that every connected FIG, G ˜ will have a SIDS whose complement is also a SIDS for which a construction to obtain a spanning subgraph of the connected FIG, G ˜ which is a tree containing only strong pairs is discussed as follows.

Construction: Consider a connected FIG, G ˜ . If G ˜ contains no cycle then trivially every pair in it is strong. If (c, cd) is an incidence pair belonging to a cycle such that ζ (c, cd) is the least among the pairs in the cycle then delete the edge cd. Then automatically the pairs (c, cd) and (d, dc) will get deleted. At each step, the pair that is considered for edge deletion will not have weight less than the weight of pair that is considered for previous edge deletion. This will result in a spanning subgraph H ˜ of G ˜ which is a tree with strong pairs. Suppose there exists a δ- pair in H ˜ say (a, ab). Then by definition of δ- pair, there will be an incidence path in G ˜ with incidence strength greater than ζ (a, ab). But the path together with (a, ab) forms a cycle in which (a, ab) is the weakest pair which is not possible according to the construction. Hence this H ˜ is the required spanning subgraph.

Theorem 3.30. If G ˜ is a connected FIG, then there exists a SIDS whose complement is also a SIDS.

Proof. Since G ˜ is a connected FIG by the construction in Remark 3.29, there exists a spanning subgraph H ˜ which is a tree with strong pairs. Hence every vertex in H ˜ will dominate its neighbors. Let u be any vertex in H ˜ . If S ˜ is taken as set of vertices that are at even distance from u then S ˜ c is set of vertices at odd distance from u. Then S ˜ and S ˜ c are SIDS of G ˜ , since the strong pairs in H ˜ are strong pairs of G ˜ .

Remark 3.31. Now, consider a comparison between the SIDN, γ _IS of a FIG and the SDN, γ _S of the underlying FG.

If (c, cd) and (d, dc) are strong pairs, it need not imply that edge cd is strong. Similarly (c, cd) and (d, dc) need not be strong if edge cd is strong. Hence in general γ _IS  and γ _S are not comparable as given in Example 3.32.

Example 3.32. For the FIG in Figure 6, all pairs are strong but the edge uv is not strong. Therefore γ _S  = 0.7 and γ _IS  = 0.5.

OPEN IN VIEWER

Fig. 6

FIG with γ _S  > γ _IS .

Now for the FIG in Figure 7, all edges are strong but the pairs (v, uv) and (x, xv) are not strong. Hence, γ _S  = 0.2 and γ _IS  = 0.4 .

OPEN IN VIEWER

Fig. 7

FIG with γ _S  < γ _IS .

Proposition 3.33. For SFIG G ˜ = ( φ , ρ , ζ ) , where all the edges in the underlying fuzzy graph G are strong, γ _IS  ≤ γ _S .

Proof. Since all pairs and edges are strong in the FIG, a SIDS in G ˜ will be a SDS in G and vice versa. Therefore the result follows, since ζ (u, uv) ≤ φ (u) ∧ ρ (uv).

Example 3.34. For the FIG in Figure 8, γ _S  = γ _IS  = 0.1.

OPEN IN VIEWER

Fig. 8

FIG with γ _S  = γ _IS .

Remark 3.35. Properties of SIDS and SIDN of some FIGs are examined in the following results. The SIDN for CFIG and a complete bipartite FIG is obtained in Proposition 3.37 and in Theorem 3.39 respectively. The SIDN of a FIC, fuzzy incidence path and a cycle is examined in Theorem 3.41 and Corollary 3.42. Propositions 3.48, 3.50 and Theorem 3.49 discuss the property of SIDS in FIT.

Theorem 3.36. [20] In a FIG G ˜ , if a pair (x, xy) is an effective pair, then (x, xy) is strong.

Proposition 3.37. Let G ˜ = ( φ , ρ , ζ ) be CFIG, then γ IS = ∧ { ζ ( x , xy ) , ( x , xy ) ∈ ζ * }

Proof. Note that in a CFIG every pair is a strong pair. Hence, each vertex dominates every other vertex. Therefore each singleton {u} , u ∈ V is a SIDS in a CFIG and the weight of each SIDS, {u} is ∧ {ζ (u, uv) : v ∈ V}. Suppose (x, xy) has the least ζ value among all the pairs. Since {x} is also a SIDS, γ _IS  = ζ (x, xy). Hence γ _IS  = ∧ {ζ (x, xy) : (x, xy) ∈ ζ^*}.

Next, definition of a complete bipartite FIG is provided in Definition 3.38 and the SIDN is obtained for it in Theorem 3.39.

Definition 3.38. The FIG, G ˜ = ( φ , ρ , ζ ) is a complete bipartite FIG, if G = ( V , φ , ρ ) is fuzzy bipartite graph and for every x ∈ V₁ and y ∈ V₂, xy ∈ ρ^*, ζ (x, xy) = φ (x) ∧ ρ (xy) and ζ (y, xy) = φ (y) ∧ ρ (xy).

Theorem 3.39. For a complete bipartite FIG, G ˜ the SIDN, γ _IS  = 2 (∧ {ζ (x, xy) : (x, xy) ∈ ζ^*}).

Proof. Note that by the definition of a complete bipartite FIG, all pairs (x, xy) in G ˜ are effective pairs. Let V₁ and V₂ be the partitions of V of the complete bipartite FIG, G ˜ . Since all the pairs in G ˜ are effective they are strong. Each vertex in V₁ dominates every vertex in V₂ and vice versa. Therefore all the sets of the form {u, v} such that u ∈ V₁ and v ∈ V₂ are SIDS. Suppose that (x, xy) has the least ζ value in G ˜ . Since all pairs are effective ζ (x, xy) = ζ (y, xy). Hence, {x, y} will be a minimum SIDS and, γ _IS  = 2 (∧ {ζ (x, xy) : (x, xy) ∈ ζ^*}).

Remark 3.40. For a graph which is either a path or a cycle on n vertices, the domination number, γ = ⌈ n 3 ⌉ . If G ˜ is a FIG which is either a FIC or a fuzzy incidence path, it cannot be asserted that the minimum SIDS will contain exactly ⌈ n 3 ⌉ vertices. Consider FIG, G ˜ with φ^* = {x, y, z} and φ (x) =0.4, φ (y) =0.3 and φ (z) =0.4, ρ (xy) =0.2, ρ (yz) =0.2. ζ (x, xy) =0.05, ζ (y, xy) =0.2, ζ (y, yz) =0.2 and ζ (z, zy) =0.05. Then the SIDN is 0.1 and minimum SIDS is {x, y}.

Theorem 3.41. If G ˜ = ( φ , ρ , ζ ) is a FIC or a fuzzy incidence path then, γ IS = ∧ { W ( S ˜ ) : S ˜ is a SIDS and | S ˜ | ≥ ⌈ n 3 ⌉ } where n = |φ^*|.

Proof. In a FIC every pair is strong. Hence each vertex dominates its neighbors. Hence ⌈ n 3 ⌉ vertices is required to dominate all the vertices in G ˜ . But for the SIDS to attain the minimum weight at least ⌈ n 3 ⌉ vertices is required. Hence the result. The proof is similar for FIG which is a fuzzy incidence path.

Corollary 3.42. Let the FIG, G ˜ = ( φ , ρ , ζ ) be a cycle then, γ IS = ∧ { W ( S ˜ ) : S ˜ and | S ˜ | ≥ ⌈ n 3 ⌉ } where n = |φ^*|.

Proof. If G ˜ is a cycle then at most one pair will be a δ- pair. If there are no δ- pairs in G ˜ , then it is a FIC. And, if there is only one δ- pair say, (x, xy), then vertices x and y will not dominate each other. Consider the spanning subgraph H ˜ = G ˜ \ xy , of G ˜ which is a fuzzy incidence path from x to y. The SIDS of H ˜ and G ˜ are the same. Hence the result follows from Theorem 3.41.

Theorem 3.43. [16] Let G ˜ be a FIT. The internal vertices of the fuzzy incidence spanning sub graph F ˜ which is a tree are the cut vertices of G ˜ .

Theorem 3.44. [16] G ˜ is a FIG. The common vertex of at least two incidence cut pairs is a FICV.

Theorem 3.45. [16] A non- trivial FIT has at least two FIENs.

Theorem 3.46. [16] Let G ˜ be a FIG. A pair is an incidence cut pair iff it is α- strong.

Theorem 3.47. [16] A connected FIG is a FIT iff it has no β- strong pairs.

Properties of SIDS in FITs are discussed in Propositions 3.48, 3.50 and in Theorem 3.49.

Proposition 3.48. Let G ˜ be a FIT with |φ^*|>1, then at least one incidence cutpair is incident at each vertex in the SIDS.

Proof. Assume that G ˜ is FIT with |φ^*|>1. Then by Theorem 3.28, every vertex in G ˜ dominates at least one distinct vertex. Hence a strong incidence pair is incident at each vertex in the SIDS. Since G ˜ is a FIT all strong incidence pairs are α- pairs. Therefore by Theorem 3.46 at least one incidence cutpair is incident at each vertex in the SIDS.

Theorem 3.49. G ˜ is a FIT with |φ^*|>1, then the set of all FICVs forms a SIDS.

Proof. Consider FITs with |φ^*|≥3. If |φ^*|=2 then the two vertices will be FIEVs. Let S ˜ be the set of all FICVs in G ˜ . Then by Theorems 3.43, 3.44 and 3.45, V \ S ˜ is the set of FIEVs. Let u ∈ V \ S ˜ . since G ˜ is a FIT, it is connected. Hence by Theorem 3.28, u dominates a vertex say v in G ˜ .

Claim: v is a FICV

Proof of claim: Suppose that v is not a FICV. Then v is FIEV. Hence v has only one strong neighbor which is uv. Then all other incidence pairs at v will be δ pairs. Since u is also a FIEV, all pairs at u except (u, uv) are δ pairs. Now, since |φ^*|≥3 there exists a y such that either uy ∈ ρ^* or vy ∈ ρ^*. Therefore, if vertex u and edge uy or vy is considered, there will not be any SIP from u to uy orto vy, which is not possible by Theorem 3.27. Hence the claim.

By the claim every FIEV is dominated by a FICV. Hence the set of all FICVs forms a SIDS.

Proposition 3.50. The set of all FIEVs in a FIT with |φ^*|>1 is a SIDS, iff every FICV has at least one FIEV as its SIN.

Proof. Assume that the set of all FIEVs say S ˜ in a FIT forms a SIDS. Let u be a FICV. Since V \ S ˜ is the set of all FICVs, u ∈ V \ S ˜ . By the definition of SIDS, every vertex in V \ S ˜ is dominated by a vertex in S ˜ . Since u is arbitrary, every FICV has at least one FIEV as its SIN.

Conversely assume that every FICV has at least one FIEV as its SIN. Let S ˜ be the set of all FIEVs. Then V \ S ˜ is set of all FICVs. By the assumption, S ˜ dominates every vertex in the FIT. Therefore S ˜ is a SIDS of the FIT.

A social application of strong incidence domination is discussed in this section. In today’s busy world, people are related to each other in one way or another. People come into contact with other people in their daily lives leading to the spread of infectious diseases. Most diseases spread through social contact. Here, the SIDS and SIDN can be used to find the minimum possibility of a group of related people getting infected by a contagious disease.

To analyze the situation, construct a FIG as follows. The vertices in set V represent people in a group, and the edge set E represents the relation between them. If a person u is related to a person v in some way, then represent this relation by an edge uv in the graph. The weight of the vertex is the extent to which he/she is exposed to the disease from outside the group. For example, if a person is a homemaker, then his/her chance of getting infected is less than that of a social worker. Now the edge weight is taken as the degree of the relationship between the people of the group. If a person u is closely related to v i.e, if u and v are related in such a way that they come in close proximity or they share a closed space for very long time then, the edge uv gets weight close to 1. The weight of the incidence pair (u, uv) is the chance of person v getting infected by u, i.e., if ζ (u, uv) =0.4, it means that the chance that u will infect v is 0.4. If person u does not take preventive measures or does not maintain social distance from others then he/she has more chance of infecting others than a person who takes all necessary precautions. By an α- pair (u, uv), it means that the chance of person v getting infected from u directly is more than the chance he/she gets infected from u indirectly. A β- pair (u, uv), means that the chance of person v getting infected from u directly is same as the chance he/she gets infected from u indirectly. Similarly, δ- pair (u, uv), means that the chance of person v getting infected from u directly is less than the chance he/she gets infected from u indirectly. An application of SIDS and SIDN to find the minimum chance of the entire group getting infected is illustrated with the help of an example as follows:

Suppose there is a group of 8 people. The vertex set, V = {p₁, p₂, p₃, . . . , p₈} where each p _i represent a person in the group. Consider the FIG in the Figure 9.

OPEN IN VIEWER

Fig. 9

Illustration of application of SID in a FIG.

For the FIG in Figure 9, all pairs except (p₆, p₆p₁) and (p₅, p₅p₂) are strong pairs. The δ- pair is not considered for domination because in the case of the pair (p₆, p₆p₁), the chance of person p₆ getting infected from p₃ is more than p₆ getting infected from p₁. Hence a vertex u dominates v only if u has more or equal chance of getting infected from v directly than getting infected from v indirectly and vise versa. Hence to find the minimum chance of the entire group getting infected, find the SIDS. Here the set D = {p₂, p₃, p₅} is a minimum dominating set with SIDN 0.8, which means that, if persons p₂, p₃ and p₅ are getting infected, then the minimum chance of entire group getting infected is 0.8.

Thus the concept of SIDS and SIDN is used to construct a FIG in which vertices represent people of a social group. The weight of a vertex is the extent to which the person is exposed to the disease. The edge weight indicates the degree of relation between the people, and weight of a pair represents the chance of a person infecting another person. The SIDN of the FIG obtained gives the minimum chance of the entire group of socially related people getting infected when the people in the SIDS get infected.

Domination in FIG is considerably a new area of research. A comparative study on different domination parameters in FIG is discussed in this section. Afsharmanesh et al.[1] defined domination in FIG using incidence valid edges, i.e, a vertex c dominates vertex d if, I ( cd ) ≥ 0.5 , ζ ( c , cd ) ≥ ρ ( cd ) 2 and ζ ( d , dc ) ≥ ρ ( cd ) 2 , where I ( cd ) = ρ ( cd ) φ ( c ) ∧ φ ( d ) . The incidence domination number is denoted by γ _i . According to Nazeer et al.[19], vertex c dominates vertex d if, pair (c, cd) is effective and the fuzzy incidence domination number is denoted by γ _FI . Nazeer et al. [20], have also defined domination using strong pair, i.e, vertex c dominates vertex d if pair (c, cd) is strong pair. The domination number in [20] is called strong pair domination number denoted by γ _s . As per the definitions in [19] and [20] the domination is not symmetric, i.e, if, c dominates d, then it need not imply that d will dominate c. Now, when a FIG is used to model a real-world problem it is not always possible to obtain a FIG with incidence valid edges or effective pairs. But in any FIG, the pairs can be categorised into strong and non strong pairs. Hence the concept of SID defined in this article can always be used in any FIG. Also, since SIDN is defined using weight of strong pairs, the least domination number is obtained using SID. As an illustration consider a FIG as in Figure 10.

OPEN IN VIEWER

Fig. 10

FIG G ˜ .

For the FIG in Figure 10, there are no incidence valid edges or effective pairs. Hence, as per [1], the minimum dominating set is the vertex set {w, x, y, z}, and γ _i  = 0.5 + 0.7 + 0.2 + 0.4 = 1.8. As per [19], the minimal dominating set is {w, x, y, z}, and γ _FI  = 1.8. Since all pairs are strong γ _s  = 0.2 + 0.4 = 0.6 and the minimal dominating set is {y, z}. Now using the concept of SID, the domination number can always be minimised since, for SIDN defined in Definition 3.8, weight of strong pair is used and ζ (c, cd) ≤ φ (c) ∧ ρ (cd). Hence a SIDS, S ˜ will be such that, S ˜ ⊂ { w , x , y , z } . Here, the only minimum SIDS is {z, y} and SIDN, γ _IS for the FIG is 0.02, which is the least compared to other domination numbers.

Domination in graphs is one of the most rigorously studied research areas, having applications in various fields. The introduction of fuzzy graphs followed by fuzzy incidence graphs opened up a vast area of research. It helped researchers to model real-world situations which were earlier considered to be difficult using graphs. This article intends to explore a new domination parameter in FIGs using the strong pairs. Strong incidence domination number is introduced using weight of strong pairs. Some bounds and properties of SIDN are discussed for FIGs. Also, SIDN and characteristics of SIDS are explored in CFIGs, complete bipartite FIGs, FIC, fuzzy incidence paths and FITs. An application of the SID is also discussed. A comparative study of different types of FIG domination is carried out.