1. INTRODUCTION

Nowadays, science and technology are characterized by complex processes and phenomena for which complete information is not always available. For such cases, mathematical models of various types of systems containing elements of uncertainty have been developed. Most of these models are based on the extension of the general set theory, namely, fuzzy sets. The concept of fuzzy sets was introduced by Zadeh [1] as a method of representing uncertainty and fuzziness. Since then, the theory of fuzzy sets has become an area of research in various disciplines.

In 1983, Atanassov [2] introduced the concept of intuitionistic fuzzy sets as a generalization of fuzzy sets. He introduced a new component to the definition of a fuzzy set, which determines the degree of nonmembership. Fuzzy sets consider the membership degree of an element in a given set (where the degree of nonmembership equals one minus the membership degree), while intuitionistic fuzzy sets operate both with a membership degree and a degree of nonmembership that are more or less independent of each other. The only restriction is that the sum of these two degrees does not exceed 1. Intuitionistic fuzzy sets are fuzzy sets of a higher order. Their application makes the solution procedure more complicated, but if the computational complexity or memory can be neglected, then a better result can be achieved.

The fuzzy graphs theory is finding an increasing number of applications for modeling real-time systems, where the level of information inherent in the system depends on different levels of accuracy. The original definition of a fuzzy graph [3] was based on fuzzy relations by Zadeh [4]. In article [5], fuzzy analogs of several basic graphical concepts were presented. In articles [6,7], the notion of fuzzy graph complement was defined, and some operations on fuzzy graphs were studied. The concepts of intuitionistic fuzzy relations and intuitionistic fuzzy graphs were introduced in articles [8,9], and some of their properties were investigated. In articles [10–12], the concepts of a dominating set, a regular independent set, a domination edge number of edges in intuitionistic fuzzy graphs were considered.

Different types of intuitionistic fuzzy graphs were considered in literature in order to cope with a diversity of practical cases: intuitionistic fuzzy competition graphs, intuitionistic fuzzy neighborhood graphs, intuitionistic fuzzy rough graphs, and others [13,14] were introduced to analyze the ecosystems and to represent the relations of competition among the species in the food web.

Some properties and features of intuitionistic fuzzy graphs were considered [15], for example, edge irregular intuitionistic fuzzy graphs, edge totally irregular intuitionistic fuzzy graphs, and others are introduced and the intuitionistic fuzzy genus graph with its genus value, strong and weak intuitionistic fuzzy genus graph are defined, as well as the isomorphism properties on intuitionistic fuzzy genus graph are discussed [16].

Some new operations on intuitionistic fuzzy graphs namely normal product and tensor product were introduced as well as the degree of the intuitionistic fuzzy graphs obtained by the operations Cartesian product, tensor product, normal product, and composition of intuitionistic fuzzy graphs [17]. Finally covering and paired domination in intuitionistic fuzzy graphs was investigates to meet different practical problems [18].

The idea of double dominating set in the intuitionistic fuzzy graph as well as lower- and upper-domination number was studied in the paper [19] and the notion of strong intuitionistic fuzzy graphs and intuitionistic fuzzy line graphs [20] were discussed.

Many practical results of applications of intuitionistic fuzzy graphs and hypergraphs were achieved in various fields of decision-making [21,22], support systems [23,24], operations research problems, for example, allocation problems, covering problems, identification of the best location, and modeling fuzzy relations between elements in graphs [25].

All the investigations show great importance and practical relevance of intuitionistic fuzzy graphs in modeling system architectures, relations between elements and data structures, solving decision-making problems [26].

However, when modeling various complex systems and processes by intuitionistic graphs, sometimes it is sufficient to use graphs that are “simpler” in their structure. Namely, the vertices of the graph are crisp and the edges are intuitionistic. Such graphs [27,28] were called intuitionistic graphs of the first kind. For example, when reflecting complex interactions and relationships between elements in a geographic information system (GIS), an intuitionistic fuzzy graph of the first kind formalizes fuzzy relations and connections between crisp objects, so that objects themselves remain static and unchanged [29,30]. The practical relevance of such an approach can be interpreted as a problem of optimal service centers allocation (finding domination set in the intuitionistic fuzzy graph) within the railway network transportation system.

Contributions. The major contributions of this paper are summarized as follows:

• Newly defined concepts termed minimal intuitionistic dominating vertex subset and domination set of the intuitionistic fuzzy graph of the first kind are formalized. These concepts are a generalization of the minimal dominating vertex subsets of a crisp graph [31] and the domination set of a fuzzy graph [32], respectively. Furthermore, a novel problem of mining of all minimal intuitionistic dominating vertex subsets from such graph is formalized.

• To address the proposed problem, a formal method for finding the minimal intuitionistic dominating vertex subset is presented. In addition, it has been proven that this method gives an exact solution (finds all minimal intuitionistic dominating vertex subsets).

• Based on the proposed method, an algorithm was developed that allows determining the domination set of the intuitionistic fuzzy graph.

The domination set and minimal intuitionistic dominating vertex subsets allow one to directly solve some optimization problems on an intuitionistic fuzzy graph. In particular, if the problem of locating centers at the vertices of an intuitionistic fuzzy graph is considered, then the domination set directly solves the problem of finding the number of centers with a given degree, and the minimal intuitionistic dominating vertex subsets allow solving the problem of optimal placement of a given number of centers with the highest degree.

2. BASIC CONCEPTS AND DEFINITIONS

It should be noted that Definition 5 is an extension of a fuzzy graph in the sense of Definition 3, in which the vertices and edges of the graph are considered not as fuzzy, but as intuitionistic sets. In the case of using a fuzzy graph in the sense of Definition 4, such a definition of an intuitionistic fuzzy graph does not make sense, since in the latter case the values μA(x)=μA(y)=1, νA(x)=νA(y)=0, and therefore, the quantity νB(x,y)=0. In this regard, we introduce the following definition:

3. DOMINATION SET OF INTUITIONISTIC FUZZY GRAPH

Let G̃=(V,U) be an intuitionistic fuzzy graph of the first kind. Let p(x,y)=(μ(x,y),ν(x,y)) be an intuitionistic fuzzy variable that determines the degree of adjacency and the degree of nonadjacency from vertex x to vertex y. Let X is an arbitrary subset of the vertices set V. For each vertex y∈V∖X, we define the volume

Figure 1

Intuitionistic fuzzy graph, X={x1,x2}

4. METHOD AND ALGORITHM FOR FINDING DOMINATION SET

We will consider the method of finding a family of all minimal intuitionistic dominating vertex subsets. The given method is similar to Maghout's method for the definition of all minimal fuzzy dominating vertex sets [32] for fuzzy graphs.

Let us assume that set Xβ is an intuitionistic dominating vertex subset of the graph G̃ with the degree of domination β=(μβ,νβ). Then for an arbitrary vertex xi∈V, one of the following conditions must be true:

1. xi∈Xβ.

2. if xi∉Xβ, then there is a vertex xj so that it belongs to set Xβ, while the vertex xj is adjacent to vertex xi with the degree (μ(xj,xi),ν(xj,xi))⩾β.

In other words, the following statement is true:

To each vertex xi∈V we assign Boolean variable pi that takes value 1, if xi∈Xβ and 0 otherwise. We assign the intuitionistic variable ξji=(μβ,νβ) for the proposition (μ(xj,xi),ν(xj,xi))⩾(μβ,νβ). Passing from the quantifier form of proposition (7) to the form in terms of logical operations, we obtain a true logical proposition:

Here, n=|V|. Supposing ξii=(1,0) and considering that the equality piV ⋁j(pj&ξji=⋁j(pj&ξji is true for any vertex xj, we finally obtain

We open the parentheses in the expression (8) and reduce the similar terms by following rules:

Here, a,b∈{0,1} and ξ1,ξ2∈[(0,1),(1,0)].

Then the expression (8) may be presented as

We can prove the next property:

We rewrite (8) as

Then in expression (12) the following statement should be fulfilled:

Therefore, all disjunctive members which do not contain variables pk+1, pk+2,…, pn, necessarily contain coefficients of the smaller value β in expression (10). From there, the disjunctive member (11) is not included in the expression (10). The received contradiction proves that subset Xβ={x1,x2,…,xk} has degree β.

We now show that the disjunctive member (11) is the minimum member. We will assume the opposite. Then should be performed condition (a) or condition (b):

1. There exists a vertex x∈Xβ such that p(x,y)>β holds for any vertex y∈V∖Xβ.

2. There is a subset X′⊂Xβ such that for any vertex y∈V∖X′ there exists a vertex x∈X′ such that p(x,y)=β.

Let the condition (a) is satisfied. Then the next statement is true:

Let's present expression ΦD in the form (12). If logic multiplication of each bracket against each other is performed without rules of absorption (9) we receive n2 disjunctive members. Moreover, each member contains exactly n elements, where each element comes from a separate bracket of decomposition (12). We will choose one of n2 disjunctive members as follows:

• element (1,0)p1 is selected from the first bracket;

• element (1,0)p2 is selected from the second bracket;

• etc.;

• element (1,0)pk is selected from the bracket k;

• from the bracket (k+1) we will select element ξi1,k+1&pi1 such, that index i1∈[1,k], and ξi1,k+1⩾β′;

• from the bracket (k+2) we will select element ξi2,k+2&pi2 such, that index i2∈[1,k], and ξi2,k+2⩾β′;

• etc.;

• from the bracket n we will select element ξin−k,n&pin−k such, that index in−k∈[1,k], and ξin−k,n⩾β′.

Using rules of absorption (9), the resulting disjunctive member can be represented as (p1&p2&…&pk&β′), where β′=ξi1,k+1&ξi2,k+2&…&ξin−k,n>β and which will be necessarily absorbed by a disjunctive member (11).

We obtained a contradiction, which proves the impossibility of case (a).

Now suppose that condition (b) is satisfied. Let's for definiteness X′={x1,x2,…,xk−1}. Considering expression ΦD in the form (12), we will choose a disjunctive member as follows:

• element (1,0)p1 is selected from the first bracket;

• element (1,0)p2 is selected from the second bracket;

• etc.;

• element (1,0)pk−1 is selected from the (k−1) bracket;

• from the bracket (k) we will select element ξi1,k&pi1 such, that index i1∈[1,k−1], and ξi1,k+1⩾β;

• from the bracket (k+1) we will select element ξi2,k+1&pi2 such, that index i2∈[1,k−1], and ξi2,k⩾β;

• etc.;

• from the bracket n we will select element ξin−k+1,n&pin−k+1 such, that index in−k+1∈[1,k−1], and ξin−k+1,n⩾β.

Using rules of absorption (9), the resulting disjunctive member can be represented as (p1&p2&…&pk−1&β′), where β′=ξi1,k&ξi2,k+1&…&ξin−k+1,n⩾β and which will be necessarily absorbed by a disjunctive member (11). We obtained a contradiction, which proves the impossibility of case (b).

Hence, Property 2 is proved.

The following algorithm for finding of intuitionistic dominating set may be proposed on the base of Property 2:

• We write proposition (8) for given intuitionistic fuzzy graph G̃.

• We simplify proposition (8) by proposition (9) and present it as a proposition (10).

• We define all minimum intuitionistic dominating vertex subsets, which correspond to the disjunctive members of proposition (10).

• We define the domination set of graph G̃.

To construct the expression (10) we rewrite the expression (8) as follows:

We convert pair aij&pj from expression (13) to weighted binary vector aij&P¯j. Here P¯j=||pi(j)|| is a binary vector that has a dimension of n. The elements of vector P¯j are defined as

The conjunction of (a1p1) and (a2p2) from expression (13) corresponds the conjunction of two weighted binary vectors a1P¯1 and a2P¯2, P¯1=||pi(1)||, P¯2=||pi(2)||, i=1,n¯, a1,a2∈[(0,1),(1,0)]. In a vector space the conjunction is defined as a1P¯1&a2P¯2=aP¯, where a=min{a1,a2}, P¯=||pi||, pi=max{pi(1),pi(2)}, i=1,n¯.

We define the operation ⩽ “less or equal” between binary vectors. Binary vector P¯1 is less or equal than P¯2 if and only if each element of P¯1 is less or equal than the corresponding element of vector P¯2. Or

Considering the algebra in space of weighted binary vectors, we can make a rule of absorption:

Now we can construct statement (10) using the conjunction operation and the rule of absorption of weighted binary vectors by Algorithm 1.

The idea of Algorithm 1 is as follows. Parentheses set of expression (13) is passed as an input. Each element of parentheses is converted to a weighted binary vector. In a loop, the vectors are multiplied together, according to the Conjunction Function (Algorithm 2), where absorption rule 14 is applied. The temporary result vector replaces the 1st vector and is used in the next iteration. In the end, the final result is taken from the 1st vector, which will determine the expression (10). That is, each element of the 1st vector defines a minimum intuitionistic dominating vertex subset with a calculated degree.

The time complexity of an algorithm is measured by the number of successive steps for its execution and is denoted by T. A step can be interpreted as an operation of binary comparison of elements.

All operations of Algorithm 2 require Nj×Mj×(n+2) comparisons. Here Nj is the number of elements in the vector V¯1; Mj is the number of compared elements in the vector V¯2 at the j-th step of calling (j=2,n¯) Algorithm 2 from Algorithm 1; (n+2) is the number of comparisons in each cycle of Algorithm 2; n is the number of vertices in the graph G̃.

Let ρ(x) be the half-degree of entry of the vertex x∈V (the number of edges that “enter” the vertex x). Let us denote by ρmax=maxx∈Vρ(x). If we estimate the complexity of the algorithm “from above,” assuming that there will be no absorptions in Algorithm 2, then we get: N2⩽ρmax, N3⩽ρmax2, …, Nn⩽ρmaxn−1, (∀j=2,n¯)Mj⩽ρmax.

This implies T⩽(ρmax2+ρmax3+ρmaxn)×(n+2)×τ, where τ is the binary comparison time. As the result, the estimation of the time complexity of the considered algorithm can be represented as O(nρmaxn).

This way we have all minimal intuitionistic dominating vertex subsets of graph G̃.

5. NUMERICAL EXAMPLE

Let's consider an example of finding the domination set of graph G̃ shown in Figure 2.

Figure 2

Intuitionistic fuzzy graph G̃.

The adjacent matrix of intuitionistic fuzzy graph G̃ looks like this:

The corresponding expression (8) for this graph has the following form:

Vectors V¯1 and V¯2 have the following form before the first iteration:

After the first iteration of the algorithm, vectors V¯1 and V¯2 have the following forms:

After completing the iterations, finally we have

So, the formula (10) for this graph has the form

It follows from the last equality that graph G̃ has 12 minimal intuitionistic dominating vertex subsets, and the domination set is defined as

This domination set shows, in particular, that there is a subset in the graph (X={x1,x4,x5,x6}), consisting of 4 vertices such that all other vertices of the graph (V∖X={x2,x3}) are adjacent to at least one vertex of the subset X with the degree at least 0.7, and not adjacent with the degree at most 0.2.

6. CONCLUSION

In this paper, we considered the concepts of fuzzy minimal intuitionistic dominating vertex subsets and a domination set of the first kind intuitionistic fuzzy graph. The method for finding all fuzzy minimal dominating vertex subsets was developed and it has been proven that this method gives an exact solution. This method is the generalization of Maghout's method for a fuzzy graph. The domination set allows estimating any intuitionistic fuzzy graph from the point of view of its invariants. It should be noted that the considered method is a method of complete ordered search since such problems can be reduced to coverage problems, that is, these problems are NP compete. However, the proposed method can be effectively used for intuitionistic fuzzy graphs without a large number of vertices.

In future research, the considered method and algorithm can be used to find other invariants, in particular, externally stable set, intuitionistic antibase, and coloring of the intuitionistic fuzzy graphs.

CONFLICTS OF INTEREST

The authors have no conflicts of interest.

AUTHORS' CONTRIBUTIONS

A. Bozhenyuk - Statement of the problem, idea of the solution method; S. Belyakov - development of an algorithm, estimation of the complexity of the algorithm; M. Knyazeva - Literature review, solution example; I. Rosenberg - Proof of the solution method.

ACKNOWLEDGMENTS

The reported study was funded by the Russian Foundation for Basic Research according to the research project N18-01-00023 and project N20-01-00197.