Cliques and clique covers in fuzzy graphs 1

1 Introduction

A graph is a representation of a set of objects where some pairs of objects are connected by links. When vagueness arises from the description of the objects or the links, a fuzzified model is needed. In 1975, Rosenfeld [28] introduced the concept of fuzzy graph. Since then, fuzzy graph theory has become a vigorous research area in both theories and applications (see [23] for a survey). As for applications, fuzzy graph theory has been found useful in modern science and technology, especially in the fields of information theory [10], neural networks [12], artificial intelligence [11], etc. On the theoretical side, various graph-theoretic concepts and theories were developed in fuzzy set theory. For instance, Rosenfeld [28] introduced the concept of fuzzy bridges, paths, cycles, trees and connectedness. Mordeson et al. [22, 24] considered fuzzy cycles, cocycles and operations on fuzzy graphs. Nair and Cheng [25] defined fuzzy cliques. Blue et al. [7] developed fuzzy shortest paths and minimum cut. Sunitha et al. [4, 33] studied blocks and stars, domination, complements of fuzzy graphs, types of arcs, node connectivity, arc connectivity, cycle connectivity and Menger’s theorem. Bhutani et al. [5, 6] investigated strong fuzzy arcs and subgraphs. Rosyida et al. [29] gave a new approach for determining fuzzy chromatic number of fuzzy graph. Samanta et al. [30, 31] discussed subclasses of fuzzy graphs such as fuzzy planar graph and m-step fuzzy competition graphs. In addition, some generalizations and subclasses of fuzzy graphs and their applications were developed (see e.g. [1–3, 31]).

Among all these existing works on fuzzy graph theory, the generalization of graph-theoretic clique (edge) cover problem in fuzzy graphs has not been touched by any researcher. The aim of this paper is to develop clique covers for fuzzy graphs. It is well known that in graph theory the subgraph induced by a clique is complete. However, according to the definition of fuzzy cliques given by Nair and Cheng [25], the fuzzy subgraph induced by a fuzzy clique is not complete (see Example 3.1). In this paper, we first modify the definition of a fuzzy clique to make sure that fuzzy cliques induce complete fuzzy subgraphs, then generalize clique covers in fuzzy graphs. The structure of the rest of this paper is organized as follows. In Section 2, we give some definitions. Section 3 is devoted to modify the definition of a fuzzy clique and characterize fuzzy cliques. In Section 4, we define fuzzy clique covers for fuzzy graphs, and give an algorithm to find a minimum fuzzy clique cover for a given fuzzy graph. Conclusions are drawn in Section 5.

2 Some basic definitions and preliminaries

We first give some notions and notations. Let n _ denote the set {1, 2, ⋯ , n} for any positive integer n and |X| denote the cardinality of the set X. For any x, y in the unit interval [0, 1], x ∨ y = max {x, y} and x ∧ y = min {x, y}. For a matrix A, A ^T and A _ij stand for the transpose and the ijth entry of A, respectively. Let G = (V, E) be an undirected graph with the vertex set V and the edge set E. An edge that connects vertices v _i and v _j in V is denoted by (v _i , v _j ). Two vertices v _i and v _j in V are adjacent if (v _i , v _j ) ∈ E. A walk of G is an alternating sequence of vertices and edges of the form v₁, (v₁, v₂), v₂, (v₂, v₃), v₃, ⋯, (v_n-1, v _n ), v _n (denoted by v₁v₂ ⋯ v _n ). A path is a walk in which no vertex is repeated. A cycle is a walk such that n ≥ 3, v₁ = v _n and v _i  ≠ v _j for any i , j ∈ n - 1 _. The length of a path or a cycle is the number of its edges.

Definition 2.1. (West [35]) A cliqueC in a graph G is a set of pairwise adjacent vertices. A maximal clique is a clique that is not a subset of any other clique. A maximum clique is a clique that has the maximum cardinality.

Notice that the subgraph induced by a clique is complete.

Definition 2.2. (Pullman [26]) A clique cover (or clique edge cover) of a graph G is a set C of cliques that includes all of the edges of G. The clique cover numbercc (G) of G is the minimum number of cliques in G needed to cover G. A minimum clique cover is a clique cover C with | C | = cc ( G ).

Definition 2.3. (Bondy et al. [8]) The union of two graphs G = (V _G , E _G ) and H = (V _H , E _H ) is the graph G ∪ H = (V _G  ∪ V _H , E _G  ∪ E _H ).

Definition 2.4. (Zadeh [36]) A fuzzy setS on a universe X is described by a membership function S : X → [0, 1]. A fuzzy relationR on X × Y is a mapping R : X × Y → [0, 1] . For two fuzzy sets A and B on X, A is a subset of B (or A is included in B), denoted by A ≤ B, if and only if A (x) ≤ B (x) for all x ∈ X.

Denote F (X) = {S : X → [0, 1]} and F (X × Y) = {R : X × Y → [0, 1]}.

Definition 2.5. (Mordeson et al. [23]) A fuzzy graphFG = (V, δ, μ) is a nonempty set V together with a fuzzy set δ ∈ F (V) and a fuzzy relation μ ∈ F (V × V) such that μ (x, y) ≤ δ (x) ∧ δ (y) for all x, y ∈ V. We call δ the fuzzy vertex set of FG and μ the fuzzy edge set of FG, respectively.

Throughout this paper, we shall assume that fuzzy graphs are undirected (i.e., the fuzzy relation μ is symmetric) and have no loops (i.e., μ (x, x) =0 for all x ∈ V). For the sake of notational convenience, we omit V (which is assumed to have n elements unless otherwise stated) in the sequel and use the notation FG = (δ, μ). The underlying graph of FG is denoted by FG^*= (δ^*, μ^*), where δ^*= {x ∈ V : δ (x) >0} and μ^*= {(x, y) ∈ V × V : μ (x, y) >0}. For any threshold t ∈ [0, 1], the t-cut of FG = (δ, μ) is FG _t  = (δ _t , μ _t ), where δ _t  = {x ∈ V : δ (x) ≥ t} and μ _t  = {(x, y) ∈ V × V : μ (x, y) ≥ t}.

Definition 2.6. (Mordeson et al. [23]) A fuzzy graph FH = (ρ, ν) is called a fuzzy subgraph of FG = (δ, μ) if ρ ≤ δ and ν ≤ μ. Moreover, it spansFG = (δ, μ) if ρ = δ.

Definition 2.7. (Mordeson et al. [23]) A fuzzy graph FH = (P, ρ, ν) is called a fuzzy subgraph of FG = (V, δ, μ) induced by P if P ⊆ V, ρ (x) = δ (x) for all x ∈ P and ν (x, y) = μ (x, y) for all x, y ∈ P. A fuzzy subgraph FH = (V, ρ, ν) induced by ρ is the maximal fuzzy subgraph of FG = (V, δ, μ) that has the fuzzy vertex set ρ (namely, ν (x, y) = ρ (x) ∧ ρ (y) ∧ μ (x, y) for all x, y ∈ V).

Definition 2.8. (Mordeson et al. [23]) A pathP in a fuzzy graph FG = (δ, μ) is a sequence of distinct vertices v₁, v₂, ⋯, v _n (n ≥ 2) such that μ (v _i , v_i+1) >0, i ∈ n - 1 _. Here, n - 1 is called the length of the path P. A path P is a cycle if v₁ = v _n and n ≥ 4. That is P = (ρ, ν) is a cycle in FG if and only if (ρ^*, ν^*) is a cycle in FG^*. A cycle P = (ρ, ν) is a fuzzy cycle if it contains more than one weakest edge (i.e., there is no unique (x, y) ∈ ν^* such that μ (x, y) = ∧ {μ (a, b) : (a, b) ∈ ν^*}).

Definition 2.9. (Sunitha et al. [33]) A fuzzy graph FG = (δ, μ) is strong if μ (x, y) = δ (x) ∧ δ (y) for all (x, y) ∈ μ^*. A fuzzy graph FG = (δ, μ) is complete if μ (x, y) = δ (x) ∧ δ (y) for all x, y ∈ δ^* and x ≠ y.

Note that a fuzzy graph is complete then it is strong, but not vice versa.

Definition 2.10. (Nair and Cheng [25]) A fuzzy subgraph FH = (ρ, ν) of FG = (δ, μ) is a fuzzy clique if FH^* is a clique and every cycle in FH is a fuzzy cycle.

Notice that Nair and Cheng took a fuzzy clique as a fuzzy subgraph, and gave the following characterization of a fuzzy clique.

Lemma 2.11. (Nair and Cheng [25]) A fuzzy subgraph FH = (ρ, ν) of FG = (δ, μ) is a fuzzy clique if and only if every cycle of length 3 in FH is a fuzzy cycle.

Definition 2.12. (Mordeson et al. [24]) The union of two fuzzy graphs FG₁ = (V₁, δ₁, μ₁) and FG₂ = (V₂, δ₂, μ₂) is FG₁ ∪ FG₂ = (V₁ ∪ V₂, δ₁ ∪ δ₂, μ₁ ∪ μ₂), where for all x ∈ V₁ ∪ V₂, (δ₁ ∪ δ₂) (x) = δ₁ (x) ∨ δ₂ (x) with δ₁ (x) =0 whenever x ∉ δ 1 * and δ₂ (x) =0 whenever x ∉ δ 2 *; for all (x, y) ∈ V₁ ∪ V₂ × V₁ ∪ V₂, (μ₁ ∪ μ₂) (x, y) = μ₁ (x, y) ∨ μ₂ (x, y) with μ₁ (x, y) =0 whenever ( x , y ) ∉ μ 1 * and μ₂ (x, y) =0 whenever ( x , y ) ∉ μ 2 *.

Definition 2.13. (Di Nola et al. [9]) The max-min compositionQ ⊙ S ∈ F (X × Z) of fuzzy relations Q ∈ F (X × Y) and S ∈ F (Y × Z) is defined by ( Q ⊙ S ) ( x , z ) = ⋁ y ∈ Y ( Q ( x , y ) ∧ S ( y , z ) ) , ∀ x ∈ X , z ∈ Z . Fuzzy relations can be represented as fuzzy matrices. In 1982, Liu [13] introduced the following decomposition problem of fuzzy matrices.

Definition 2.14. For a given n × n fuzzy matrix B, if there exists an n × p fuzzy matrix A such that B = A ⊙ A ^T , i.e., B ij = ⋁ k = 1 p ( A ik ∧ A T kj ) = ⋁ k = 1 p ( A ik ∧ A jk ) , ∀ i , j ∈ n _ , then B is called a realizable fuzzy matrix and A is called a realizing fuzzy matrix of B. Furthermore, if B is realizable, then we call the minimum value p the content of B, denoted by c (B), i.e., c (B) = min {p : B = A ⊙ A ^T , A isan n × p fuzzymatrix}.

Lemma 2.15. (Liu [14]) Let B be an n × n fuzzy matrix. Then B is realizable if and only if B _ii  ≥ B _ij  = B _ji for all i , j ∈ n _.

3 Cliques in fuzzy graphs

In graph theory, a clique induces a complete subgraph. However, according to Definition 2.10, the fuzzy subgraph induced by a fuzzy clique (namely, the fuzzy clique itself) may not be complete.

Example 3.1. Consider the fuzzy graph FG = (δ, μ) on V = {v₁, v₂, v₃, v₄} with δ (v₁) = δ (v₂) = δ (v₃) = δ (v₄) =1, μ (v₁, v₂) =0.5, μ (v₁, v₃) =0.8, μ (v₁, v₄) =0.8, μ (v₂, v₃) =0.5, μ (v₂, v₄) =0.5 and μ (v₃, v₄) =0.7, as shown in Fig. 1.

Let FH = (ρ, ν) be a fuzzy subgraph of FG such that ρ = δ, ν = μ except for ρ (v₄) =0.7 and ν (v₁, v₄) =0.7, as shown in Fig. 2.

From Lemma 2.11, we know FH is a fuzzy clique. However, it is not complete since 0.8 = ν (v₁, v₃) ≠ ρ (v₁) ∧ ρ (v₃) =1.

Here we modify the definition of a fuzzy clique so that the fuzzy subgraph induced by each fuzzy clique is complete.

Definition 3.2. In a fuzzy graph FG = (δ, μ), a subset ρ of δ is called a fuzzy clique if the fuzzy subgraph induced by ρ is complete.

Remark 3.3. In graph theory, a clique C in an undirected graph G = (V, E) is a subset of vertices such that every two distinct vertices are adjacent. That is the subgraph of G induced by C is complete. Given a clique C, connecting pairs of vertices in C with edges, one can obtain the subgraph induced by C. Conversely, for a complete subgraph G₁, the clique, which induces G₁, is just the vertex set of G₁. Therefore, the term clique may also refer to the subgraph directly in some cases. In order to generalize cliques in fuzzy graph theory, Nair and Cheng [25] introduced fuzzy cliques in fuzzy graphs. They took fuzzy cliques as fuzzy subgraphs. However, according to their definition, fuzzy cliques are not complete (see Example 3.1). Moreover, there exists no such similar relationships between fuzzy cliques and complete fuzzy subgraphs as that between cliques and complete subgraphs. Based on Definitions 2.7 and 2.9, we modify the definition of fuzzy cliques. Our modified definition can fill these gaps (see Example 3.5).

Remark 3.4. A clique in a graph can be viewed as a special case of a fuzzy clique. Indeed, let FG = (V, δ, μ) be a fuzzy graph such that δ (x) ∈ {0, 1} and μ (x, y) ∈ {0, 1} for all x, y ∈ V. Since a characteristic function fully characterizes a set, it is synonymous of the notion of a set. Then we have FG = FG^*. Let FH = (V, ρ, ν) be the fuzzy subgraph induced by a fuzzy clique ρ with ρ (x) ∈ {0, 1} for all x ∈ V. Then μ (x, y) = ρ (x) ∧ ρ (y) ∧ μ (x, y) = ν (x, y) = ρ (x) ∧ ρ (y) =1 for any x, y ∈ ρ = ρ^* and x ≠ y. Therefore ρ is a clique in FG^*.

Example 3.5. Consider the fuzzy graph FG = (δ, μ) in Example 3.1. We can verify that the subset ρ of δ with ρ (v₁) =0.8, ρ (v₂) =0.5, ρ (v₃) =0.8 and ρ (v₄) =0.7 is a fuzzy clique in FG since the fuzzy subgraph FH = (ρ, ν) induced by ρ is complete, see Fig. 3.

Obviously, FH can be completely determined by ρ, and ρ is the vertex set of FH.

We now give an application of fuzzy cliques.

Example 3.6. There are pieces of boards of different lengths and densities (see Table 1).

Now we choose some of them to make a water barrel, if the densities of two boards have a big difference (i.e., the difference is greater than or equal to 0.1), then the two boards can not be used in the same barrel. It is obvious that the barrel’s capacity for storing water is determined by the lowest piece of board in the barrel. Take boards as vertices, if two boards can be used in the same barrel, then there is an edge between them. Then the information about making a barrel can be summarized in the following fuzzy graph (see Fig. 4), where the values stand for the corresponding barrels’ capacities (measured by length) for storing water.

The fuzzy clique ρ with ρ (v₁) =0.9, ρ (v₂) =0.7 and ρ (v₃) =0.8 shows that we can use Board I, Board II and Board III to make a barrel, and the corresponding barrel’s capacity for storing water is 0.7 m.

In order to avoid confusion, we use a f-clique to identify the notion of a fuzzy clique in Definition 2.10. In what follows, we shall discuss the relationships among f-cliques, fuzzy cliques and complete fuzzy graphs.

Theorem 3.7. Each complete fuzzy subgraph is a f-clique.

Proof. Let FH = (ρ, ν) be a complete fuzzy subgraph. For any cycle abca (a, b, c ∈ ρ^*) of length 3 in FH, since FH is complete, we have ν (a, b) = ρ (a) ∧ ρ (b), ν (b, c) = ρ (b) ∧ ρ (c) and ν (a, c) = ρ (a) ∧ ρ (c). Then ν (a, b) ∧ ν (b, c) ∧ ν (a, c) = ρ (a) ∧ ρ (b) ∧ ρ (c). Without loss of generality, suppose that ρ (a) = ρ (a) ∧ ρ (b) ∧ ρ (c). Then ν (a, b) = ν (a, c) = ρ (a), i.e., there exist two weakest edges (a, b) and (a, c) in the cycle abca. Therefore abca is a fuzzy cycle. Hence, by Lemma 2.11, FH is a f-clique.□

Corollary 3.8. The fuzzy subgraph induced by a fuzzy clique is a f-clique.

Proof. According to Definition 3.2, the fuzzy subgraph induced by a fuzzy clique is complete. Then by Theorem 3.7, it is a f-clique.□

Note that Example 3.1 shows that the converse of Theorem 3.7 is not true in general. However, we have the following theorem.

Theorem 3.9. Each strong f-clique is complete.

Proof. Let FH = (ρ, ν) be a strong f-clique. It is obvious that FH^* is a clique. Then for any a, b ∈ ρ^*, we have (a, b) ∈ ν^*. Since FH is strong, it follows that ν (a, b) = ρ (a) ∧ ρ (b). Therefore ν (a, b) = ρ (a)   ∧  ρ (b) for any a, b ∈ ρ^*, i.e., FH is complete.□

We now give the characterization of a fuzzy clique.

Theorem 3.10. In a fuzzy graph FG = (δ, μ), a subset ρ of δ is a fuzzy clique if and only if ρ (x) ∧ ρ (y) ≤ μ (x, y) for all x, y ∈ ρ^* and x ≠ y.

Proof. Suppose that ρ is a fuzzy clique in FG and FH = (ρ, ν) is the fuzzy subgraph induced by ρ. By Definition 3.2, FH is complete. Then from Definitions 2.7 and 2.9, we have ρ (x) ∧ ρ (y) = ν (x, y) = ρ (x) ∧ ρ (y) ∧ μ (x, y) ≤ μ (x, y) for all x, y ∈ ρ^* and x ≠ y.

Conversely, let ρ be a subset of δ such that ρ (x) ∧ ρ (y) ≤ μ (x, y) for all x, y ∈ ρ^*, x ≠ y, and FH = (ρ, ν) be the fuzzy subgraph induced by ρ. From Definition 2.7 it follows that ν (x, y) = ρ (x) ∧ ρ (y) ∧ μ (x, y) for all x, y ∈ ρ^*. Then by the assumption ρ (x) ∧ ρ (y) ≤ μ (x, y), we have ν (x, y) = ρ (x) ∧ ρ (y). Therefore FH is complete, i.e., ρ is a fuzzy clique.□

The following corollaries are two consequences of Theorem 3.10.

Corollary 3.11. Let ρ be a fuzzy clique in FG = (δ, μ). Then for each t ∈ (0, 1], ρ _t is a clique in FG _t .

Proof. Since ρ is a fuzzy clique in FG, it follows from Theorem 3.10 that ρ (x) ∧ ρ (y) ≤ μ (x, y) for all x, y ∈ ρ^* and x ≠ y. Then for any two vertices x, y ∈ ρ _t , μ (x, y) ≥ ρ (x) ∧ ρ (y) ≥ t, i.e., (x, y) ∈ μ _t . Therefore ρ _t is a clique in FG _t .□

Corollary 3.12. Let ρ be a fuzzy clique in FG = (δ, μ). Then each nonempty subset ϱ of ρ is a fuzzy clique in FG.

Proof. This is immediate from Theorem 3.10 since ϱ (x) ≤ ρ (x) for any x ∈ V.□

In the following, we shall give another characterization of a fuzzy clique. For a fuzzy graph FG = (δ, μ), define an n × n fuzzy matrix M _FG by ( M FG ) ij = { δ ( v i ) , i = j , μ ( v i , v j ) , i ≠ j .

For a subset ρ of δ, define an n × 1 fuzzy vector V _ρ by ( V ρ ) i = { ρ ( v i ) , v i ∈ ρ * , 0 , v i ∉ ρ * . Let X FG = { X = ( x i ) i ∈ n _ T with x i ∈ [ 0 , 1 ] : X ⊙ X T≤M _FG }. Then we have:

Theorem 3.13. If ρ is a fuzzy clique of a fuzzy graph FG = (δ, μ), then V ρ ∈ X FG. Conversely, for any X = ( x i ) i ∈ n _ T ∈ X FG, the fuzzy set ρ with ρ (v _i ) = x _i for all i ∈ n _ is a fuzzy clique.

Proof. Let ρ be a fuzzy clique in FG. Then fromTheorem 3.10 it follows that ( V ρ ⊙ V ρ T ) ij = ( V ρ ) i ∧ ( V ρ ) j = ρ ( v i ) ∧ ρ ( v j ) ≤ μ ( v i , v j ) = ( M FG ) ij for anyi, j ∈ n _ with i ≠ j, and ( V ρ ⊙ V ρ T ) ii = ( V ρ ) i ∧ ( V ρ ) i = ρ ( v i ) ≤ δ ( v i ) = ( M FG ) ii for any i ∈ n _. Therefore V ρ ∈ X FG.

Conversely, for any X = ( x i ) i ∈ n _ T ∈ X FG, define a fuzzy set ρ such that ρ (v _i ) = x _i for all i ∈ n _. Since ρ (v _i ) = x _i  ≤ (M _FG )  _ii  = δ (v _i ) for all i ∈ n _, we have ρ ≤ δ. Moreover, from Theorem 3.10 it follows that ρ is a fuzzy clique in FG since ρ (v _i ) ∧ ρ (v _j ) = x _i  ∧ x _j   ≤   (M _FG )  _ij   =  μ (v _i , v _j ) for any i, j ∈ n _ with i  ≠  j. □

Notice that Theorem 3.13 generalizes the corresponding results in [32] for cliques since a clique is a special case of a fuzzy clique.

The following example will illustrate Theorem 3.13.

Example 3.14. Consider the fuzzy graph FG = (δ, μ) and the fuzzy clique ρ in Example 3.5. We have M FG = ( 1 0.5 0.8 0.8 0.5 1 0.5 0.5 0.8 0.5 1 0.7 0.8 0.5 0.7 1 ) and V ρ = ( 0.8 0.5 0.8 0.7 ) . It can be checked that V ρ ⊙ V ρ T = ( 0.8 0.5 0.8 0.7 0.5 0.5 0.5 0.5 0.8 0.5 0.8 0.7 0.7 0.5 0.7 0.7 ) ≤ M FG, i.e., V ρ ∈ X FG. Conversely, we can verify that (0.5, 0.5, 0.5 , 0.5 ) T ∈ X FG. Then the fuzzy set ϱ with ϱ (v _i ) =0.5 for all i ∈ 4 _ is a fuzzy clique of FG.

Recall Corollary 3.12, it shows that each nonempty subset of a fuzzy clique is also a fuzzy clique. It is quite natural to ask what the upper bound is. We now give the definitions of maximal and maximum fuzzy cliques.

Definition 3.15. A fuzzy clique ρ in a fuzzy graph FG = (δ, μ) is maximal if there is no fuzzy clique σ in FG such that ρ < σ. A maximal fuzzy clique ρ is maximum if it posses the largest possible size of |ρ^*|.

Example 3.16. Consider the fuzzy graph FG = (δ, μ) shown in Fig. 5.

We can check that σ = {σ (v₁) =0.7, σ (v₂) =0.3, σ (v₃) =0.4, σ (v₄) =0.5}, ϱ = {ϱ (v₁) =0.7, ϱ (v₂) =0.5, ϱ (v₃) =0.4, ϱ (v₄) =0.3} and ρ = {ρ(v₁) =0.4, ρ (v₂) =0.3, ρ (v₃) =0.8, ρ (v₄) =0.4} are fuzzy cliques in FG, and they are both maximal and maximum. The fuzzy clique φ ={φ (v₁) =0.7, φ (v₃) =0.4, φ (v₄) =0.5} in FG is maximal but not maximum.

Using Theorem 3.13, we can characterize maximal fuzzy cliques.

Theorem 3.17. In a fuzzy graph FG = (δ, μ), a subset ρ of δ is a maximal fuzzy clique if and only if V _ρ is a maximal element in X FG.

Proof. By Theorem 3.13, ρ is a fuzzy clique if and only if V ρ ∈ X FG. Furthermore, if ρ is maximal, then V _ρ is maximal in X FG, and vice versa.□

Theorem 3.18. Let ρ be a maximal fuzzy clique in FG = (δ, μ). Then ⋀_x∈ρ^*ρ (x) = ⋀ _y,z∈ρ^*μ (y, z).

Proof. Suppose that ρ is a maximal fuzzy clique in FG = (δ, μ). Then by Theorem 3.10, ρ (x) ∧ ρ (y) ≤ μ (x, y) for any x, y ∈ ρ^*. Therefore ⋀_x∈ρ^*ρ (x) ≤ ⋀ _y,z∈ρ^*μ (y, z). Let ρ (v _k ) = ⋀ _x∈ρ^*ρ (x) and μ (v _i , v _j ) = ⋀ _y,z∈ρ^*μ (y, z). We shall prove that ρ (v _k ) = μ (v _i , v _j ). Suppose to the contrary that ρ (v _k ) < μ (v _i , v _j ). Define a fuzzy set σ such that σ = ρ except for σ (v _k ) = μ (v _i , v _j ). Obviously, σ > ρ. Moreover, σ ≤ δ since σ (v _k ) = μ (v _i , v _j ) = ⋀ _y,z∈ρ^*μ (y, z) ≤ μ (v _k , z) ≤ δ (v _k ) ∧ δ (z) ≤ δ (v _k ) for any z ∈ ρ^*. Now we shall show that σ is a fuzzy clique, i.e., σ (y) ∧ σ (z) ≤ μ (y, z) for any y, z ∈ ρ^*. It is obvious that σ (y) ∧ σ (z) = ρ (y) ∧ ρ (z) ≤ μ (y, z) when v _k  ∉ {y, z}. If v _k  ∈ {y, z}, without loss of generality let v _k  = z, then σ (y) ∧ σ (z) = ρ (y) ∧ μ (v _i , v _j ) ≤ μ (v _i , v _j ) = ⋀ _u,v∈ρ^*μ (u, v) ≤ μ (y, z). Therefore σ is a fuzzy clique, which contradicts the assumption that ρ is maximal. Thus ⋀_x∈ρ^*ρ (x) = ⋀ _y,z∈ρ^*μ (y, z).□

Corollary 3.19. Let ρ be a maximal fuzzy clique in FG = (δ, μ), FH = (ρ, ν) be the fuzzy subgraph induced by ρ and ⋀_x,y∈ρ^*μ (x, y) = μ (v _i , v _j ). Then ν (v _i , v _j ) = μ (v _i , v _j ).

Proof. It is evident that ν (v _i , v _j ) ≤ μ (v _i , v _j ). If ν (v _i , v _j ) < μ (v _i , v _j ), then ρ (v _i ) ∧ ρ (v _j ) = ν (v _i , v _j ) < μ (v _i , v _j ). Therefore ⋀_x∈ρ^*ρ (x)≤ ρ (v _i ) ∧ρ (v _j ) < μ (v _i , v _j ) = ⋀ _x,y∈ρ^*μ (x, y), which contradi-cts Theorem 3.18. Thus ν (v _i , v _j ) = μ (v _i , v _j ).□

Theorem 3.20. Let ρ be a maximal fuzzy clique in FG = (δ, μ). Then there is at least one x ∈ ρ^* such that ρ (x) = δ (x).

Proof. Let ρ be a maximal fuzzy clique in FG = (δ, μ). Obviously, ρ (x) ≤ δ (x) for all x ∈ ρ^*. Assume to the contrary that ρ (x) < δ (x) for all x ∈ ρ^*. Define V₁ = {x ∈ ρ^*: ρ (x) ≤ ⋀ _y∈ρ^*μ (x, y)} and V₂ = {x ∈ ρ^*: ρ (x) > ⋀ _y∈ρ^*μ (x, y)}. Then ρ^*=V₁ ∪ V₂. On one hand, if V₁ = ρ^*, pick an arbitrary x₀ ∈ V₁ and construct a fuzzy set σ such that σ (x) = ρ (x) whenever x ≠ x₀ and σ (x₀) = δ (x₀), then σ > ρ. Moreover, by Theorem 3.10, σ is a fuzzy clique since σ (x) ∧ σ (x₀) = ρ (x) ∧ σ (x₀) ≤ ⋀ _y∈ρ^*μ (x, y) ∧ δ (x₀) ≤ μ (x, x₀) ∧ δ (x₀) ≤ μ (x, x₀) for any x ∈ V₁ - x₀, and σ (x) ∧ σ (y) = ρ (x) ∧ ρ (y) ≤ μ (x, y) for any x, y ∈ V₁ - x₀. Therefore we get a fuzzy clique σ and σ > ρ which contradicts the maximality of ρ. On the other hand, if V₁ ≠ ρ^*, i.e., V₂≠ ∅, pick some x₀ ∈ V₂ such that ρ (x₀) = max {ρ (x) : x ∈ V₂} and define a fuzzy set ϱ with ϱ (x) = ρ (x) except for ϱ (x₀) = δ (x₀), then ϱ > ρ. It can be verified that ϱ is a fuzzy clique. Indeed, ϱ (x) ∧ ϱ (x₀) = ρ (x) ∧ δ (x₀) ≤ ⋀ _y∈ρ^*μ (x, y) ∧ δ (x₀) ≤ μ (x, x₀) ∧ δ (x₀) ≤ μ (x, x₀) when x ∈ V₁, ϱ (x) ∧ ϱ (x₀) = ρ (x) ∧ δ (x₀) = ρ (x) = ρ (x) ∧ ρ (x₀) ≤ μ (x, x₀) when x ∈ V₂, and ϱ (x) ∧ ϱ (y) = ρ (x) ∧ ρ (y) ≤ μ (x, y) when x, y ∈ ρ^*- x₀. Then by Theorem 3.10, ϱ is a fuzzy clique such that ϱ > ρ, a contradiction. Therefore ρ (x) < δ (x) can not hold for all x ∈ ρ^*. Then there is at least one x ∈ ρ^* such that ρ (x) = δ (x).□

Here we should point out that the converses of Theorems 3.18, 3.20 and Corollary 3.19 may not hold, see the following example.

Example 3.21. Consider the fuzzy graph FG =(δ, μ) in Example 3.16. As for the fuzzy clique φ ={φ (v₁) =0.7, φ (v₂) =0.3, φ (v₃) =0.3, φ (v₄) =0.3} and the fuzzy subgraph FH = (φ, ν) induced by φ, we can check that φ (v₂) = φ (v₃) = φ (v₄) = ⋀ _x∈ρ^*φ (x) = ⋀ _y,z∈ρ^*μ (y, z) = μ (v₂, v₃), ν (v₂, v₃) =μ (v₂, v₃) and φ (v₁) = δ (v₁). However, φ is not maximal since σ = {σ (v₁) =0.7, σ (v₂) =0.3, σ (v₃) =0.4, σ (v₄) =0.5} and ϱ = {ϱ (v₁) =0.7, ϱ (v₂) =0.5, ϱ (v₃) =0.4, ϱ (v₄) =0.3} are fuzzy cliques such that σ > φ and ϱ > φ.

4 Clique covers in fuzzy graphs

In this section, we shall discuss fuzzy clique covers and minimum fuzzy clique covers in fuzzy graphs, and provide an algorithm to find a minimum fuzzy clique cover of a given fuzzy graph.

Definition 4.1. A fuzzy clique edge cover of a fuzzy graph FG = (δ, μ) is a set FC of fuzzy cliques that includes all of the fuzzy edges in FG.

Notice that in graphs, a clique cover of a graph G “covers” all of the edges in G, then certainly covers all of the vertices in G. However, according to Definition 4.1, a fuzzy clique edge cover of a fuzzy graph FG may not “cover” some fuzzy vertices in FG. See the following example.

Example 4.2. Consider the fuzzy graph FG = (δ, μ) given below (see Fig. 6).

We can check that σ = {σ (v₁) =0.3, σ (v₂) =0.2, σ (v₃) =0.3} and ρ = {ρ (v₁) =0.5, ρ (v₂) =0.5, ρ (v₄) =0.2} are two fuzzy cliques in FG. The two fuzzy subgraphs induced by σ and ρ are shown in Fig. 7.

From Definition 4.1, we know {σ, ρ} is a fuzzy edge clique cove of FG since all of the fuzzy edges in FG have been included by {σ, ρ}. However, the fuzzy vertex δ (v₁) =0.6 is not covered by {σ, ρ}.

Now, we shall define a fuzzy clique cover of a fuzzy graph which covers all of the fuzzy edges and fuzzy vertices.

Definition 4.3. A fuzzy clique cover of a fuzzy graph FG = (δ, μ) is a set FC of fuzzy cliques such that FG can be decomposed as the union of all the fuzzy subgraphs induced by the fuzzy cliques in FC. The fuzzy clique cover number of FG, denoted by cc (FG), is the minimum cardinality of a fuzzy clique cover of FG. A minimum fuzzy clique cover is a fuzzy clique cover FC such that | FC | = cc ( FG ).

Example 4.4. Consider the fuzzy graph FG in Example 4.2. According to Definition 4.3, the fuzzy clique edge cover {σ, ρ} in Example 4.2 is not a fuzzy clique cover since the union of the two fuzzy subgraphs induced by σ and ρ is not FG (see Fig. 8).

We can check that σ = {σ (v₁) =0.3, σ (v₂) =0.2, σ (v₃) =0.3} and ϱ = {ϱ (v₁) =0.6, ϱ (v₂) =0.5, ϱ (v₄) =0.2} are two fuzzy cliques of FG. The two fuzzy subgraphs induced by σ and ϱ are shown in Fig. 9.

The union of the two fuzzy subgraphs induced by σ and ϱ is FG. Therefore {σ, ϱ} is a fuzzy clique cover. Moreover, {σ, ϱ} is a minimum fuzzy clique cover.

In what follows, we shall characterize a minimum fuzzy clique cover of a fuzzy graph. We first give two lemmas.

Lemma 4.5. For a fuzzy clique ρ in a fuzzy graph FG = (δ, μ), the composition V ρ ⊙ V ρ T represents the fuzzy subgraph induced by ρ.

Proof. Let ρ be a fuzzy clique in a fuzzy graph FG and FH = (ρ, ν) be the fuzzy subgraph induced by ρ. Define an n × n fuzzy matrix M _FH as (M _FH )  _ij  = ν (v _i , v _j ) whenever i ≠ j, and (M _FH )  _ii  = ρ (v _i ). Then, for any i , j ∈ n _, we have ( V ρ ⊙ V ρ T ) ij = ( V ρ ) i ∧ ( V ρ ) j = ρ ( v i ) ∧ ρ ( v j ) = ν ( v i , v j ) = ( M FH ) ij when i ≠ j, and ( V ρ ⊙ V ρ T ) ii = ( V ρ ) i ∧ ( V ρ ) i = ρ ( v i ) = ( M FH ) ii. Therefore V ρ ⊙ V ρ T = M FH, i.e., V ρ ⊙ V ρ T represents FH.□

Example 4.6. Consider the fuzzy graph FG in Example 4.2. We know that ρ = {ρ (v₁) =0.5, ρ (v₂) =0.5, ρ (v₄) =0.2} is a fuzzy clique in FG. Then V ρ ⊙ V ρ T = ( 0.5 0.5 0 0.2 0.5 0.5 0 0.2 0 0 0 0 0.2 0.2 0 0.2 ) represents the fuzzy subgraph induced by ρ (see the right part of Fig. 7).

Lemma 4.7. For two fuzzy cliques ρ and σ in a fuzzy graph FG = (δ, μ), the composition ( V ρ V σ ) ⊙ ( V ρ V σ ) T represents the union of the two fuzzy subgraphs induced by ρ and σ.

Proof. It is obvious that ( V ρ V σ ) ⊙ ( V ρ V σ ) T = ( V ρ V σ ) ⊙ ( V ρ T V σ T ) = ( V ρ ⊙ V ρ T ) ∨ ( V σ ⊙ V σ T ).Then, by Definition 2.12 and Lemma 4.5, ( V ρ V σ )⊙ ( V ρ V σ ) T represents the union of the two fuzzy subgraphs induced by ρ and σ.□

Example 4.8. Consider the fuzzy graph FG in Example 4.2. We can see that σ = {σ (v₁) =0.3, σ (v₂) =0.2, σ (v₃) =0.3} and ρ = {ρ (v₁) =0.5, ρ (v₂) =0.5, ρ (v₄) =0.2} are two fuzzy cliques in FG. Then ( V ρ V σ ) ⊙ ( V ρ V σ ) T = ( 0.5 0.3 0.5 0.2 0 0.3 0.2 0 ) ⊙ ( 0.5 0.5 0 0.2 0.3 0.2 0.3 0 ) = ( 0.5 0.5 0.3 0.2 0.5 0.5 0.2 0.2 0.3 0.2 0.3 0 0.2 0.2 0 0.2 )

represents the union of the two fuzzy subgraphs induced by σ and ρ (see Fig. 8).

Theorem 4.9. For a fuzzy graph FG, if { σ k : k ∈ m _ } is a fuzzy clique cover of FG, then the n × m matrix RM _FG with (RM _FG )  _ik  = σ _k  (v _i ) for all k ∈ m _ and v _i  ∈ V, i ∈ n _, is a realizing fuzzy matrix of M _FG .

Proof. For a fuzzy clique cover { σ k : k ∈ m _ } of FG, define the n × m matrix RM _FG by (RM _FG )  _ik  = σ _k  (v _i ) for all k ∈ m _ and v _i  ∈ V, i ∈ n _. Then by Lemma 4.7, RM FG ⊙ RM FG T represents the fuzzy graph FG, i.e., RM _FG is a realizing fuzzy matrix of M _FG .□

Example 4.10. Consider the fuzzy graph FG inExample 4.2. We can check that σ₁ = {σ₁ (v₁) =0.3, σ₁ (v₂) =0.2, σ₁ (v₃) =0.3} and σ₂ = {σ₂ (v₁) =0.6, σ₂ (v₂) =0.5, σ₂ (v₄) =0.2} are fuzzy cliques of FG, and {σ₁, σ₂} is a fuzzy clique cover of FG. Then by Theorem 4.9, RM FG = ( 0.3 0.6 0.2 0.5 0.3 0 0 0.2 ) is a realizing fuzzy matrix of M FG = ( 0.6 0.5 0.3 0.2 0.5 0.5 0.2 0.2 0.3 0.2 0.3 0 0.2 0.2 0 0.2 ).

Theorem 4.9 shows that for a fuzzy graph FG, we can construct a realizable fuzzy matrix RM _FG of M _FG from a fuzzy clique cover of FG. In fact, the converse also holds.

Theorem 4.11. For a fuzzy graph FG, if RM _FG is an n × m realizing fuzzy matrix of M _FG , then { σ k : k ∈ m _ } with σ _k  (v _i ) = (RM _FG )  _ik for all v _i  ∈ V, i ∈ n _ and k ∈ m _, is a fuzzy clique cover of FG.

Proof. From the definition of M _FG , we have (M _FG )  _ii  ≥ (M _FG )  _ij  = (M _FG )  _ji for all i , j ∈ n _. Then by Lemma 3.15, M _FG is realizable. Let RM _FG be an n × m realizing fuzzy matrix of M _FG . Construct fuzzy sets σ _k , k ∈ m _, such that σ _k  (v _i ) = (RM _FG )  _ik for all v _i  ∈ V, i ∈ n _. Then by Theorem 3.13, σ _k is a fuzzy clique for any k ∈ m _. From Lemma 4.7 it follows that the union of all the fuzzy subgraphs induced by σ _k , k ∈ m _, is FG since RM FG ⊙ RM FG T = M FG. Therefore { σ k : k ∈ m _ } is a fuzzy clique coverof FG.□

Theorem 4.12. For a fuzzy graph FG, { σ k : k ∈ cc ( FG ) _ } is a minimum fuzzy clique cover of FG if and only if RM _FG is an n × c (M _FG ) realizing fuzzy matrix of M _FG , where (RM _FG )  _ik  = σ _k  (v _i ) for all k ∈ cc ( FG ) _ = c ( M FG ) _, v _i  ∈ V, i ∈ n _.

Proof. It is obvious from Theorems 4.9 and 4.11.□

Remark 4.13. Theorems 4.9, 4.11 and 4.12 generalize the corresponding results given in [32]. Consider the fuzzy graph FG shown in Fig. 10.

From the definition of M _FG , we have M FG = ( 1 1 0 0 1 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 1 ). It is easy to check that M FG = ( 1 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 1 1 0 0 ) ⊙ ( 1 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 1 1 0 0 ) T and c (M _FG ) =3. Then by Theorem 4.12, {σ₁, σ₂, σ₃} is a minimumfuzzy clique cover of FG, where σ₁ = {σ₁ (v₁)= 1, σ₁ (v₂) =1, σ₁ (v₅) =1, σ₁ (v₇) =1}, σ₂ = {σ₂(v₃) =1, σ₂ (v₄) =1} and σ₃ = {σ₃ (v₂) =1, σ₃ (v₆)= 1}. Assuming σ i = σ i * for all i ∈ 3 _, we know {σ₁, σ₂, σ₃} is a minimum clique cover of the graph FG^*= FG.

Roberts [27] showed that the intersection number of a graph equals to the clique cover number of the graph, and discussed applications of the intersection number in a traffic lights problem. Now, we apply fuzzy clique covers to the traffic lights problem.

Example 4.14. Consider the traffic intersection with several labeled traffic streams, as shown in Fig. 11. Some pairs of traffic streams are compatible in the sense that they could receive green lights at the same time. To have traffic move safely and efficiently, what is the smallest number of time periods needed?

The compatibility information of the traffic intersection is summarized in the compatibility graph G shown in Fig. 12, where the vertices of G are the traffic streams, and two streams are joined by an edge if and only if they are compatible.

As Roberts [27] points out, determining the minimum time periods needed is equivalent to minimizing the clique cover numbers of all spanning subgraphs of G. We can check that the graph FG (FG^*= FG) shown in Fig. 10 is a spanning subgraph of G, and its clique cover number is minimum. From Remark 4.13, we know {{v₁, v₂, v₅, v₇} , {v₃, v₄} , {v₂, v₆}} is a minimum clique cover of FG. So we need at least three time periods.

Remark 4.15. Note that cc (FG) ≠ cc (FG^*) in general. For example, consider the fuzzy graph FG shown in Fig. 13.

It is easy to check that σ = {σ (v₁) =0.4, σ (v₂) =0.2, σ (v₃) =0.5} and ρ = {ρ (v₁) =0.6, ρ (v₃) =0.4} are two fuzzy cliques in FG, and {σ, ρ} is a minimum fuzzy clique cover of FG. Then we have cc (FG) =2, while cc (FG^*) =1.

Theorem 4.16. For each fuzzy graph FG, cc (FG) ≥ cc (FG^*).

Proof. It is easy to verify that for a fuzzy clique cove { σ k : k ∈ m _ } of FG, the set { σ k * : k ∈ m _ } is a clique cover of FG^*. Therefore cc (FG) ≥ cc (FG^*).□

Theorem 4.17. For each strong fuzzy graph FG = (δ, μ), cc (FG) = cc (FG^*).

Proof. Using Theorem 4.16, we just need to prove that for any clique cover C of FG^*, there exists a fuzzy clique cover FC of FG such that | FC | = | C |. Let C = { C 1 , ⋯ , C m } be a clique cover of FG^*. For any C k ∈ C, define σ _k as σ k ( v i ) = { δ ( v i ) , v i ∈ C k , 0 , v i ∉ C k . Obviously, σ k * = C k. Since FG is strong, we have σ _k  (v _i ) ∧ σ _k  (v _j ) = δ (v _i ) ∧ δ (v _j ) = μ (v _i , v _j ) for any v _i , v _j  ∈ C _k . Then by Theorem 3.10, σ _k is a fuzzy clique. Now we shall show that FC = { σ k : k ∈ m _ } is a fuzzy clique cover of FG. Indeed, for any (v _i , v _j ) ∈ μ^*, there is a clique C k ∈ C such that v _i , v _j  ∈ C _k , then σ _k  (v _i ) ∧ σ _k  (v _j ) = μ (v _i , v _j ), i.e., the fuzzy edge μ (v _i , v _j ) is “covered” by the fuzzy clique σ _k . Moreover, for any v _i  ∈ δ^*, there is some C _k such that v _i  ∈ C _k , then δ (v _i ) = σ _k  (v _i ), i.e., the fuzzy vertex δ (v _i ) is “covered” by σ _k . Therefore FC is a fuzzy clique cover of FG, which implies that cc (FG) ≤ cc (FG^*). Using Theorem 4.16, we have cc (FG) = cc (FG^*). □

The following example illustrates Theorem 4.17.

Example 4.18. Consider the strong fuzzy graph FG shown in Fig. 14.

It is quite evident that {C₁ = {v₁, v₂} , C₂ = {v₁, v₃}} is a minimum clique cover of FG^*. Then by Theorem 4.17, {σ₁, σ₂} is a minimum fuzzy clique cover of FG, where σ₁ = {σ₁ (v₁) =0.6, σ₁ (v₂) =0.5} and σ₂ = {σ₂ (v₁) =0.6, σ₂ (v₃) =0.4}.

Based on Theorems 4.9, 4.11 and 4.12, we now give an algorithm for finding a minimum fuzzy clique cover of a fuzzy graph.

Algorithm 4.19. Computing a minimum fuzzy clique cover of a fuzzy graph.

Step 1. Input a fuzzy graph FG = (δ, μ).

Step 2. Construct an n × n fuzzy matrix M _FG with ( M FG ) ij = { δ ( v i ) , i = j , μ ( v i , v j ) , i ≠ j .

Step 3. Find an n × c (M _FG ) realizing fuzzy matrix RM _FG of M _FG (see [21, 34]).

Step 4. Construct fuzzy cliques σ _k , k ∈ c ( M FG ) _, such that σ _k  (v _i ) = (RM _FG )  _ik .

Step 5. Output the minimum fuzzy clique cover { σ k : k ∈ c ( M FG ) _ } of FG.

Notice that Wang [34] has proved that for a realizable fuzzy matrix M, an n × c (M) realizing fuzzy matrix of M can be found within 1 ^{n 2} + 2 ^{n 2} + ⋯ + c (M) ^{n 2} steps. Therefore, a minimum fuzzy clique cover of a fuzzy graph FG can be found within 1 ^{n 2} + 2 ^{n 2} + ⋯ + c (M _FG ) ^{n 2} steps. Moreover, finding a minimum fuzzy clique cover in a fuzzy graph is NP-complete since finding a minimum clique cover in a graph is NP-complete (see [20, 26]).

Example 4.20. Consider the fuzzy graph FG = (δ, μ) shown in Fig. 15.

We have M FG = ( 0.7 0.4 0 0.3 0.3 0.4 0.5 0.2 0.4 0.5 0 0.2 0.8 0 0 0.3 0.4 0 0.4 0.4 0.3 0.5 0 0.4 0.5 ). It is easy to check that RM FG = ( 0.7 0 0 0.4 0.5 0.2 0 0 0.8 0.3 0.4 0 0.3 0.5 0 ) is a realizing matrix of M _FG and c (M _FG ) =3. Then we can construct fuzzy cliques σ₁ = {σ₁ (v₁) =0.7, σ₁ (v₂) =0.4, σ₁ (v₄) =0.3, σ₁ (v₅) =0.3}, σ₂= {σ₂ (v₂) =0.5, σ₂ (v₄) =0.4, σ₂ (v₅) =0.5} and σ₃ = {σ₃ (v₂) =0.2, σ₃ (v₃) =0.8}.

From Fig. 16, it can be seen that the union of the fuzzy subgraphs induced by σ₁, σ₂ and σ₃ is FG. Therefore {σ₁, σ₂, σ₃} is a minimum fuzzy clique cover of FG.

At the end of this section, we give an application of fuzzy clique covers in a gas transportation network.

Example 4.21. Consider the gas transportation network shown as the fuzzy graph in Fig. 17, where vertices represent gas tanks, edges represent pipelines and values represent abilities to withstand pressures.

For receiving gas, each gas tank can be connected to an external device. The one connected to the outside is called an initial point and these ones receiving gas from the initial point are named terminal points. During the process of gas transportation, the initial point and the terminal points must be directly connected to each other (i.e., all these points form a clique). In order to store as much gas as possible, what is the smallest number of initial points?

According to the requirements for transportation, the smallest number of initial points can be derived from a minimum fuzzy clique cover of FG by minimizing the cardinality of {v _{i 1} , ⋯ , v _{i cc(FG)} }, where v _{i k} , k ∈ cc ( FG ) _, is a maximum vertex (i.e., a vertex that gets the maximum degree) of σ _k , and {σ₁, ⋯ , σ_cc(FG)} is a minimum fuzzy clique cover of FG. We can check that {σ₁, σ₂, σ₃} with σ₁ = {σ₁ (v₂) =0.3, σ₁ (v₃) =1, σ₁ (v₅) =0.2}, σ₂ = {σ₂(v₁) =0.8, σ₂ (v₂) =0.5, σ₂ (v₄) =0.4, σ₂ (v₅) =0.4} and σ₃ = {σ₃ (v₂) =0.6, σ₃ (v₄) =0.5, σ₃ (v₅)= 0.6} is a minimum fuzzy clique cover of FGwhich minimizes the cardinality of {v _{i 1}  = v₃, v _{i 2}  = v₁, v _{i 3}  = v₂}. Therefore we need at least 3 initial points v₃, v₁ and v₂ (or v₅).

5 Conclusions

Fuzzy graphs can be viewed as generalizations of graphs. In graph theory, finding a minimum clique cover is a well-known NP-complete problem. This paper developed fuzzy clique covers in fuzzy graphs and gave an algorithm to find a minimum fuzzy clique cover of a fuzzy graph.