Number of possible captures in a chess puzzle move using the fuzzy colouring technique

1 Introduction

The graph colouring issue has several applications, including creating a schedule or timetable, assigning mobile radio frequencies, sudoku, resource allocation, and map colouring. Many graph-theoretic problems are inherently ambiguous. Rosenfeld [12] developed the concept of fuzzy graphs in 1975 to solve this problem. Later, additional research in the area of fuzzy graphs occurred.

One of the most popular areas of the fuzzy graph is colouring. Munoz et al. [10] introduced the fuzzy graph colouring in 2005. Additionally, they described the fuzzy subset as the chromatic number of a fuzzy graph. Eslachi and Onagh [4] defined k-fuzzy colouring and fuzzy chromatic number χ ^f  (G) in 2006. In terms of threshold graphs, Anjaly and Sunitha [5] introduced the chromatic number of a fuzzy graph in 2014. In 2015, Pramanik et al. defined fuzzy colouring [11], a novel concept for colouring fuzzy graphs. They also defined fuzzy chromatic number γ (G) of the fuzzy graph G using fuzzy colouring and identified the relationship between χ (G) and γ (G).

In 2000, J.N. Mordeson and P.S. Nair [9] defined various fuzzy graph operations such as union, Join, and cartesian product. In 2016, Anjaly and Sunitha [9] discovered a relationship between the chromaticity of fuzzy graphs and the chromaticity of the resultant fuzzy graphs obtained by performing various operations on fuzzy graphs such as union, join, and various types of products, using the definition given by Anjaly and Sunitha in [5]. However, no research has been done on the relation between the fuzzy chromatic numbers of two fuzzy graphs and the fuzzy chromatic number of the resultant fuzzy graphs generated by performing specified operations with fuzzy colouring. We use the fuzzy colouring approach to determine the relationship between the fuzzy chromatic number of fuzzy graphs and the resultant fuzzy graphs by applying various operations union, join, and newly developed operations. The strong edge product, power of a fuzzy graph, and u-product are some of the additional operations we developed. An application also provided using fuzzy colouring to calculate the number of possible captures in a chess puzzle.

2 Preliminaries

Definition 2.1. [9, 12] A fuzzy graph G = (V, σ, μ) is an algebraic structure of nonempty set V together with a pair of functions σ : V ⟶ [0, 1] and μ : V × V ⟶ [0, 1] such that for all x, y ∈ V, μ (x, y) ≤ σ (x) ∧ σ (y) and μ is a symmetric fuzzy relation on σ. Here, ∧ denotes the minimum.

The underlying crisp graph of G is denoted by G^* : (σ^*, μ^*), where σ^* = {v ∈ V ∣ σ (v) >0} and μ^* = {(u, v)∈ V × V ∣μ (u, v) >0}. We assume the fuzzy graph G with no loops and a finite and nonempty set V. Additionally, σ^* = V .

Definition 2.2. [2] For a fuzzy graph G = (V, σ, μ), a path from x to y is a sequence of nodes P : x = x₀, x₁, x₂,  . . , x _n  = y such that σ (x _i ) >0 and σ (x _i  - 1)∧ σ (x _i ) ≥ μ (x _i  - 1, x _i ) >0 for all i. min i μ ( x i - 1 , x i ) is called the strength of P. The maximum of the strengths of all paths in G from x to y is called strength of connectedness between x and y, denoted by CONN _G  (x, y).

Let G - (x, y) be the fuzzy graph obtained from G by replacing μ (x, y) by 0. we call the arc (x, y) strong in G if μ (x, y) >0 and μ (x, y) ≥ CONN_G-(x,y) (x, y). A Path P : x₀, x₁, x₂, . . . , x _n is called strong if (x_i-1, x _i ) is strong for all i. A strong path P from x to y is an x - y geodesic if there is no shorter strong path from x to y and the length of an x - y geodesic is the distance from x to y denoted by d _g  (x, y).

Definition 2.3. [4] For a fuzzy graph G = (V, σ, μ), an edge (x, y), x, y ∈ V is called strong if 1 2 { σ ( x ) ∧ σ ( y ) ≤ μ ( x , y ) } , and it is called weak otherwise.

We represent weak edges by dotted lines and strong edges by plain lines. Note that we didn’t separate the weak and strong edges in Figs. 5 and 6 since it is not required.

Pramanik et al. [11] defined fuzzy colours as the mixing of colours as follows:

Definition 2.4. [11] Let C = {c₁, c₂, . . . , c _n } , n ≥ 1 be a set of basic colours. The fuzzy set (C, f) is called the set of fuzzy colours, where f : C ⟶ [0, 1] with f (c _i ) the membership value of the colour c _i is the amount per unit standard mixture. The colour c i ˜ = ( c i , f ( c i ) ) is called the fuzzy colour corresponding to the basic colour c _i .

We can create different fuzzy colours starting from a basic colour according to the preceding concept of fuzzy colour. Red, for example, is a fundamental colour. By combining 0.9 unit red colour with 0.1 unit white colour, a fuzzy red can be created. If two vertices are connected by a strong edge, then they have distinct basic colours in this approach. Otherwise, they adopt various fuzzy colours [11].

In [11], Pramanik et al. described the fuzzy colouring procedure in detail.

Definition 2.5. [11] The chromatic number of fuzzy colouring is the minimum number of basic colours needed to colour a fuzzy graph and is called the fuzzy chromatic number. The fuzzy chromatic number of a fuzzy graph G is denoted by γ (G) .

Definition 2.6. [1] A isomorphism between two fuzzy graphs G₁ and G₂ is a bijective map ψ : V₁ → V₂ that satisfies σ₁ (x) = σ₂ (ψ (x)) for all x in V and μ₁ (x, y) = μ₂ (ψ (x) , ψ (y)) for all x, y in V and we write G₁ ≈ G₂ .

3 Fuzzy chromatic number of fuzzy graph resultants

Definition 3.1. [9] If G₁ = (V₁, σ₁, μ₁) and G₂ = (V₂, σ₂, μ₂) are two disjoint fuzzy graphs with G 1 * = ( V 1 , E 1 ) and G 2 * = ( V 2 , E 2 ) , then G₁ ∪ G₂ is the fuzzy graph (V₁ ∪ V₂, σ, μ), where σ ( u ) = { σ 1 ( u ) , u ∈ V 1 - V 2 σ 2 ( u ) , u ∈ V 2 - V 1 . ∥ μ ( u , v ) = { μ 1 ( u , v ) , ( u , v ) ∈ E 1 - E 2 μ 2 ( u , v ) , ( u , v ) ∈ E 2 - E 1 .

Theorem 3.1. For disjoint fuzzy graphs G₁ = (V₁, σ₁, μ₁) and G₂ = (V₂, σ₂, μ₂), γ (G₁ ∪ G₂) = max {γ (G₁) , γ (G₂)} .

Proof. G₁ ∪ G₂ : (V₁ ∪ V₂, σ, μ) denotes the union of two fuzzy graphs G₁ and G₂. If (u, v) is a strong edge in G _i , i = 1, 2, then it also has a strong edge in G₁ ∪ G₂. If (u, v) is a weak edge in G _i , i = 1, 2, then the same is true in G₁ ∪ G₂. There is no edge between G₁ and G₂; the colouring of G₁ vertices is independent of G₂ vertices in G₁ ∪ G₂. Similarly, the colouring of vertices in V₂ is unaffected by the colouring of vertices in V₁. As a result, γ (G₁ ∪ G₂) will be the maximum of γ (G₁) and γ (G₂).

Definition 3.2. [9] The join of disjoint fuzzy graphs G₁ and G₂ is G₁ + G₂ = (V₁ ∪ V₂, σ, μ), where σ = σ₁ + σ₂ and μ = μ₁ + μ₂ are fuzzy subsets of V₁ ∪ V₂ and E₁ ∪ E_{2 ^∪E′, where is the set of all edges joining V1} and V₂, σ ( u ) = { σ 1 ( u ) , u ∈ V 1 σ 2 ( u ) , u ∈ V 2 . and μ ( u , v ) = { μ 1 ( u , v ) , μ 2 ( u , v ) , σ 1 ( u ) ∧ σ 2 ( v ) , ( u , v ) ∈ E 1 , ( u , v ) ∈ E 2 , ( u , v ) ∈ E .

Theorem 3.2. Let G₁ = (V₁, σ₁, μ₁) and G₂ = (V₂, σ₂, μ₂) be two fuzzy graphs. Then, γ (G₁ + G₂) = γ (G₁) + γ (G₂) .

Proof. First, the vertices of G₁ are coloured. Let {c₁, c₂, . . . , c _n } be the set of basic colours used to colour the vertices of V₁ in G₁ + G₂. In addition to these colours, we have to check how many basic colours are needed to colour other vertices of G₁ + G₂, i.e. V₂, and verify whether it is equal to γ (G₂). The proof is by mathematical induction.

Note that in G₁ + G₂, the behaviour of the edges of G₁ and G₂ are the same. However, edges in (edges joining V₁ and V₂) are strong since for then 1 2 { σ ( x ) ∧ σ ( y ) ≤ σ ( x ) ∧ σ ( y ) ≤ μ ( x , y ) } . p(k): Let G₂ be a connected fuzzy graph with k edges; then, γ (G₁ + G₂) = γ (G₁) + γ (G₂). Case 1: if k = 0, i.e. G₂ has only one vertex (say, a).

Because ‘a’ establishes strong edges with all vertices of G₁, we must choose another basic colour different from c₁, c₂, . . . , c _n to colour the vertex ‘a’ in G₁ + G₂. Thus, p(k) is true for k=0. Case 2: If k = 1 That is, G ₂ has only one edge [see (a,b)]. Then, it will be either a strong or weak edge.

Thus, p(k) is true for k=1

Case 3: k = 2 If G₂ has two edges, then the following options are presented in Fig. 1. If G₂ is (A), then in G₁ + G₂, ‘a’ and ‘c’ are not adjacent, whereas they both have an adjacency with vertices in V₁. Thus, ‘a’ and ‘c’ can choose the same basic colour, say c_n+1, which is different from the colours c₁, c₂, . . . , and c _n , and ‘b’ will be coloured by another c_n+2 since ‘b’ has an adjacency with ‘a’ and ‘c’. Colour ‘a’ and ‘c’ with a basic colour, then colour ‘b’ with another basic colour when colouring G₂.

OPEN IN VIEWER

Fig. 1

G₁ for Case 3.

⇒γ (G₁ + G₂) = γ (G₁) +2 = γ (G₁) + γ (G₂)

In G₁ + G₂, if G₂ is (B), colour ‘a’ has a basic colour other than the colours from the collection {c₁, c₂, . . . , c _n }. We cannot colour ‘b’ with a basic colour because (a,b) is a weak edge even if it generates strong edges with all vertices of V₁. As a result, ‘b’ will obtain a fuzzy colour. When colouring ‘c’, we have two options: ‘c’ can use the basic colour of ‘a’ because squoa’ and ‘c’ are not adjacent and ‘c’ produces a strong edge with all G₁ vertices, or ‘c’ can use a fuzzy colour of ‘a’. The chromaticity does not alter in any instance. While colouring G₂ independently, we can colour ‘a’ with a basic colour and then colour ‘b’ and ‘c’ with the fuzzy colour of ‘a’. While colouring G₁ + G₂, keep in mind that the number of basic colours used to colour the fuzzy graph G₂ is equal to the number of additional basic colours added to the collection {c₁, c₂, . . . , c _n }.

Because edge (a,b) is strong, two additional colours other than c₁, c₂, . . . , c _n are required in the case of (C). Furthermore, ‘c’ will inherit the fuzzy colour of ‘b’s basic colour. When colouring (C), the same technique is used.

Therefore, in each case, γ (G₁ + G₂) = γ (G₁) + γ (G₂)

Thus, p(k) is valid for k=2.

case 4: k = 3, i.e. G₂ has 3 edges

If G₂ is isomorphic to (E), (F), (G), (H), and (I) in Fig. 2. Then, the colouring technique is the same as in Case 3.

OPEN IN VIEWER

Fig. 2

G₂ for Case 4.

If G₂ is (A) in addition to the set of basic colours {c₁, c₂, . . . , c _n }, then we need three more basic colours to colour the rest of the vertices of G₁ + G₂ since all edges are strong edges in G₂ and three vertices made adjacency with each other. Note that the fuzzy chromatic number of G₂ is three. Thus, γ (G₁ + G₂) = γ (G₁) + γ (G₂)

We require one more basic colour if G₂ is (B) in addition to the set of basic colours {c₁, c₂, . . . , c _n }. Because ‘a’ is adjacent to all of G₁’s vertices, they are all strong edges. Since (a,b) is weak, we cannot colour ‘b’ with a basic colour even though ‘b’ also establishes strong edges with all vertices of G₁. As a result, ‘b’ will obtain a fuzzy colour. Note that (a,c) is a weak edge, so ‘c’ will also colour by a fuzzy colour. When we individually colour the fuzzy graph (B). First, ‘a’ will be given a basic colour, while the other two will be given the fuzzy colour of ‘a’. As a result, the number of basic colours added to this set {c₁, c₂, . . . , c _n } is the same as the number of basic colours used in the colouring of (B). In the cases of (C) and (D), two extra basic colours are required in addition to the colours c₁, c₂, . . .  c _n and γ (C) = γ (D). Therefore, the result γ (G₁ + G₂) = γ (G₁) + γ (G₂) holds. Thus, p(k) is valid for k=3.

Suppose this result is true for ‘k’ number of edges. Assume G₂ has (k+1) edges, the (k + 1)  ^th of which is (x, y). Then,

γ ((G₁ + G₂) - (x, y)) = γ (G₁) + γ (G₂ - (x, y)) (by assumption)

When colouring (G₁ + G₂), the number of basic colours added to the (G₁ + G₂) - (x, y) set of basic colours is the same as the number of basic colours added to γ (G₂ - (x, y)) when colouring G₂. Thus, γ (G₁ + G₂) = γ (G₁) + γ (G₂)

As a result of mathematical induction, the result is valid for all k. If G₂ is not connected, then the same procedure can be used for each component.

Example 3.1. Consider the two fuzzy graphs G₁ and G₂ with the respective fuzzy chromatic numbers 2 and 1 shown in Fig. 3. The same figure indicates that their joint’s fuzzy chromatic number is 3, equal to γ (G₁) + γ (G₂).

OPEN IN VIEWER

Fig. 3

Fuzzy chromatic numbers of G₁, G₂ and G₁ + G₂ for Example 3.1.

Definition 3.3. [13] The complement of a fuzzy graph G : (V, σ, μ) is the fuzzy graph G ¯ : ( V , σ ¯ , μ ¯ ) with σ ¯ ( u ) = σ ( u ) and μ ¯ ( u , v ) = σ ( u ) ∧ σ ( v ) - μ ( u , v ) .

Theorem 3.3. Let G : (V, σ, μ) be a fuzzy graph, and G ¯ : ( V , σ ¯ , μ ¯ ) be its complement. Then, edge (u, v) is strong if either (u, v) is not an edge or (u, v) is a weak edge in G ¯ .

Proof. Suppose (u, v) is a strong edge; then, 1 2 ( σ ( u ) ∧ σ ( v ) ) ≤ μ ( u , v )(1)case 1: μ (u, v) = σ (u) ∧ σ (v)

⇒ μ ¯ ( u , v ) = 0 (by definition).

⇒ (u, v) is not an edge in G ¯ .

case 2: μ (u, v) < σ (u) ∧ σ (v)

claim: (u, v) is a weak edge in G ¯

If suppose not, then 1 2 ( σ ¯ ( u ) ∧ σ ¯ ( v ) ) ≤ μ ¯ ( u , v )

⇒ 1 2 ( σ ( u ) ∧ σ ( v ) ) ≤ σ ( u ) ∧ σ ( v ) - μ ( u , v ) (by definition)

⇒ μ ( u , v ) ≤ σ ( u ) ∧ σ ( v ) - 1 2 ( σ ( u ) ∧ σ ( v ) )

Thus, μ ( u , v ) ≤ 1 2 ( σ ( u ) ∧ σ ( v ) )(2) from Equations (1) and (2) μ ( u , v ) = 1 2 ( σ ( u ) ∧ σ ( v ) ) for all edges, which is a contradiction. Thus, (u, v) is a weak edge in G ¯ .

Conversely, assume either (u, v) is not an edge in G ¯ or (u, v) is a weak edge in G ¯

case 1: (u, v) is not an edge in G ¯

⇒ μ ¯ ( u , v ) = 0

⇒σ (u) ∧ σ (v) - μ (u, v) =0 which implies μ (u, v) = σ (u) ∧ σ (v)

⇒ 1 2 ( σ ( u ) ∧ σ ( v ) ) ≤ ( σ ( u ) ∧ σ ( v ) ) = μ ( u , v )

⇒ (u, v) is a strong edge in G

case 2: (u, v) is a weak edge in G ¯

⇒ 1 2 ( σ ¯ ( u ) ∧ σ ¯ ( v ) ) > μ ¯ ( u , v ) > σ ( u ) ∧ σ ( v ) - μ ( u , v ) ⇒ 1 2 ( σ ( u ) ∧ σ ( v ) ) > σ ( u ) ∧ σ ( v ) - μ ( u , v ) ⇒ 1 2 ( σ ( u ) ∧ σ ( v ) ) < μ ( u , v ) Thus, (u, v) is a strong edge.

Hence, this is proven.

Proposition 3.1. γ ( G + G ¯ ¯ ) ≤ γ ( G + G ¯ )

Proof. In G + G ¯ , the joined edges between G and G ¯ are strong, whereas they are weak in G + G ¯ ¯ . Note that each vertex in G + G ¯ is an end vertex of a strong edge, whereas in G + G ¯ ¯ , each vertex is an end vertex of a weak edge. Thus, G + G ¯ ¯ having a fuzzier colour than G + G ¯ implies γ ( G + G ¯ ¯ ) ≤ γ ( G + G ¯ ) .

Example 3.2. Consider the fuzzy graph G shown in Fig. 4 with γ (G) =1 and γ ( G ¯ ) = 2 values. We can see in the same figure that γ ( G + G ¯ ¯ ) ≤ γ ( G + G ¯ ) .

OPEN IN VIEWER

Fig. 4

Fuzzy graphs for Example 3.2.

Proposition 3.2. If G₁ ≈ G₂ and if (u, v) is a strong edge(or weak edge) in G₁ then the corresponding edge (ψ (u) , ψ (v)) is also strong edge (or weak edge) in G₂.

Proof. Suppose G₁ ≈ G₂. Let (u, v) is a strong edge in G₁ 1 2 ( σ 2 ( ψ ( u ) ) ∧ σ 2 ( ψ ( v ) ) ) = 1 2 ( σ 1 ( u ) ∧ σ 1 ( v ) ) ≤ μ 1 ( u , v ) = μ 2 ( ψ ( u ) , ψ ( v ) ) Thus the corresponding edge (ψ (u) , ψ (v)) of (u, v) is a strong edge in G₂

Similarly, in the case of weak edges.

Remark 3.1. If G₁ ≈ G₂ then by using Proposition 3.2 it is clear that γ (G₁) = γ (G₂) .

We develop some additional fuzzy graph operations and compare the fuzzy chromatic number of the resultant fuzzy graphs to their corresponding fuzzy graphs.

Definition 3.4. k ^th power The k ^th power G ^k  : (V, σ ^k , μ ^k ) of the fuzzy graph G has V (G ^k ) = V (G), and u and v are adjacent in G ^k whenever d _g  (u, v) ≤ k.

σ k ( u ) = σ ( u ) μ k ( u , v ) = σ ( u ) ∧ σ ( v )

Example 3.3. Let G be the fuzzy graph in Fig. 5. Then, in the same figure, we can see that the G² of G, the 2 ^th power of G, is a fuzzy graph.

OPEN IN VIEWER

Fig. 5

Fuzzy graph G and G² in Example 3.3.

Theorem 3.4. k ^th power G ^k  : (V, σ ^k , μ ^k ) of a fuzzy graph G is a fuzzy graph.

Proof. Let G : (V, σ, μ) be a fuzzy graph. For the vertices u, v in G satisfying d _g  (u, v) ≤ k, μ ^k  (u, v) = σ (u) ∧ σ (v) = σ ^k  (u) ∧ σ ^k  (v). Hence μ ^k  (u, v) ≤ σ ^k  (u) ∧ σ ^k  (v). Therefore, G ^k is a fuzzy graph.

Theorem 3.5. γ (G ^k  ≥ γ (G) .

Proof. 1 2 ( σ k ( u ) ∧ σ k ( v ) ) ≤ σ k ( u ) ∧ σ k ( v ) = σ ( u ) ∧ σ ( v ) = μ k ( u , v )

All edges are strong edges; thus, γ (G ^k  ≥ γ (G). Existing edges become strong edges, and newly formed edges are also strong; thus, the result holds.

Remark 3.2. If k₁ ≥ k₂ then γ (G ^{k ₁}  ≥ γ (G ^{k ₂} ) .

Definition 3.5. u- product Let G₁ = (V₁, σ₁, μ₁) and G₂ = (V₂, σ₂, μ₂) be two disjoint fuzzy graphs. For a fixed u ∈ V₁, the u- product G₁₂ (u) is the fuzzy graph G = (V₁ × V₂, σ, μ), where

E = {(uv₁, uv₂) ∣ (v₁, v₂) ∈ E₂} ∪ {u₁w, u₂w) ∣ (u₁, u₂) ∈ E₁, w ∈ V₂} σ ( uv ) = σ ( u ) ∧ σ ( v ) ∀ ( uv ) ∈ V 1 × V 2 μ ( uv 1 , uv 2 ) = σ ( u ) ∧ μ ( v 1 , v 2 ) , ( v 1 , v 2 ) ∈ E 2 for fixed u ∈ V 1 μ ( u 1 w , u 2 w ) = σ ( w ) ∧ μ ( u 1 , u 2 ) , ( u 1 , u 2 ) ∈ E 1 , w ∈ V 2 Note: for a v ∈ G₂, we can also define v-product G₂₁ (v) .

Example 3.4. Let G₁ = (V₁, σ₁, μ₁) and G₂ = (V₂, σ₂, μ₂) be two disjoint fuzzy graphs represented in Fig. 6. Then in the same figure we can see that G₁₂ (d) of G₁ and G₂, which is a fuzzy graph.

OPEN IN VIEWER

Fig. 6

Fuzzy graphs G₁, G₂ and their d- product in Example 3.4.

Theorem 3.6. u- product of two disjoint fuzzy graphs is a fuzzy graph.

Proof. Let G₁ = (V₁, σ₁, μ₁) and G₂ = (V₂, σ₂, μ₂) be two disjoint fuzzy graphs. For a fixed u ∈ V₁, consider the u- product G₁₂ (u). From the Definition 3.5, for the fixed u ∈ V₁ and (v₁, v₂) in E₂ μ ( uv 1 , uv 2 ) = σ ( u ) ∧ μ ( v 1 , v 2 )(3) = σ ( u ) ∧ μ ( v 1 , v 2 ) ∧ σ ( u )(4) ≤ σ ( u ) ∧ σ ( v 1 ) ∧ σ ( v 2 ) ∧ σ ( u )(5) = σ ( uv 1 ) ∧ σ ( uv 2 )(6) Similarly, for (u₁, u₂) ∈ E₁ and w ∈ V₂

μ ( u 1 w , u 2 w ) = σ ( w ) ∧ μ ( u 1 , u 2 )(7) = σ ( w ) ∧ μ ( u 1 , u 2 ) ∧ σ ( w )(8) ≤ σ ( w ) ∧ σ ( u 1 ) ∧ σ ( u 2 ) ∧ σ ( w )(9) = σ ( u 1 w ) ∧ σ ( u 2 w )(10)

From Equations (6) and (10), it is clear that G₁₂ (u) is a fuzzy graph.

Theorem 3.7. γ (G₁₂ (u) ≤ γ (G₁) + γ (G₂) -1 .

Proof. G₁ and G₂’s u-product is made by pasting G₁ on G₂, |V₂| times at each vertex of G₂ through the vertex ‘u’ of G₁. To colour G₁₂ (u) and G₂, then each G₁ at the end vertices of G₂, and maximum γ (G₁) -1 colours are needed. Thus, γ (G₁₂ (u) ≤ γ (G₁) + γ (G₂) -1 .

Remark 3.3. if u ≠ v then γ (G₁₂ (u)) need not be equal to γ (G₁₂ (v)) .

Definition 3.6. Strong edge product Let G₁ = (V₁, σ₁, μ₁) and G₂ = (V₂, σ₂, μ₂) be two disjoint fuzzy graphs. The strong edge product G₁ G₂ of G₁ and G₂ is the fuzzy graph G = (V₁ × V₂, σ, μ), where E = {(uv₁, uv₂) ∣ (v₁, v₂) ∈ E₂, (v₁, v₂) is a strong edge } ∪ {u₁w, u₂w) ∣ (u₁, u₂) ∈ E₁, (u₁, u₂) is a strong edge } σ ( uv ) = σ ( u ) ∧ σ ( v ) μ ( uv 1 , uv 2 ) = σ ( u ) ∧ μ ( v 1 , v 2 ) μ ( u 1 w , u 2 w ) = σ ( w ) ∧ μ ( u 1 , u 2 )

Example 3.5. Let G₁ = (V₁, σ₁, μ₁) and G₂ = (V₂, σ₂, μ₂) be two disjoint fuzzy graphs represented in Fig. 7. Then in the same figure we can see that G₁G₂ of G₁ and G₂, which is a fuzzy graph.

OPEN IN VIEWER

Fig. 7

Fuzzy graphs G₁, G₂ and their strong edge product.

Theorem 3.8. The strong edge product of two disjoint fuzzy graphs is a fuzzy graph.

Proof. Let G₁ = (V₁, σ₁, μ₁) and G₂ = (V₂, σ₂, μ₂) be two disjoint fuzzy graphs. For a fixed u ∈ V₁, consider the strong edge product G₁G ₂ of G₁ and G₂. From the Definition 3.6, for u ∈ V₁ and a strong edge (v₁, v₂) in E₂ μ ( uv 1 , uv 2 ) = σ ( u ) ∧ μ ( v 1 , v 2 )(11) = σ ( u ) ∧ μ ( v 1 , v 2 ) ∧ σ ( u )(12) ≤ σ ( u ) ∧ σ ( v 1 ) ∧ σ ( v 2 ) ∧ σ ( u )(13) = σ ( uv 1 ) ∧ σ ( uv 2 )(14) Similarly, for the strong edge (u₁, u₂) ∈ E₁ and w ∈ V₂ μ ( u 1 w , u 2 w ) = σ ( w ) ∧ μ ( u 1 , u 2 )(15) = σ ( w ) ∧ μ ( u 1 , u 2 ) ∧ σ ( w )(16) ≤ σ ( w ) ∧ σ ( u 1 ) ∧ σ ( u 2 ) ∧ σ ( w )(17) = σ ( u 1 w ) ∧ σ ( u 2 w )(18) From Equations (14) and (18), it is clear that G₁ epsfboxGG₂ is a fuzzy graph.

Theorem 3.9. If G₁ has no cycles and G₂ has at least one edge, then γ (G₁ G₂) = γ (G₂).

Proof.

The result is trivial if G₁ has no edges. Assume G₁ contains only two vertices (say a and b) that are connected by a strong edge (a, b). Let V₂ = {u₁, u₂, . . . , u _n } be the set of G₂ vertices, and let {c₁, c₂, . . . , c _m } denote the set of G₂ basic colours. G₂ repeats 2 times in G₁G₂ with two sets of vertices: {au₁, au₂, . . . , au _n }, and {bu₁, bu₂, . . . , bu _n }. For each i = 1, 2, . . . , n, there is an edge from au _i to bu _i . Furthermore, those edges are strong. We can colour {au₁, au₂, . . . , au _n } in G₁ G₂ using the same set of basic colours {c₁, c₂, . . . , c _m } of G₂. Additionally, we can colour the set {bu₁, bu₂, . . . , bu _n } with the same set of colours so that au _i and bu _i have different colours. Thus, γ (G₁ G₂) = γ (G₂).

Let V₁ = {v₁, v₂, . . . , v _k } be the set of vertices of G₁ and V₂ = {u₁, u₂, . . . , u _n } be the set of vertices of G₂. The graph of G₂ repeats |V₁| times in G₁ G₂. Colour each set of vertices {v _i u₁, v _i u₂, . . . , v _i u _n } for each i with G₂’s basic colours so that no two adjacent vertices v _i u _k and v _j u _k for i ≠ j have the same colour. This is possible because G₁ does not have any cycles. Thus, γ (G ₁ G₂) = γ (G₂).

Number of possible captures in a chess puzzle by using fuzzy colouring.

Fuzzy graphs represent some problems nicely. One of them is a chess puzzle. There are so many online chess sites which provide learning chess games. The chess puzzles category is more prominent among players who would like to improve their ability in the chess game. At the end of each game, some online chess sites will provide a computer analysis of our movements using graphs. So it is helpful to understand our mistakes, blunders, and accuracy in each step. Capturing the opposite pieces is one strategy in the chess game to win. The existing chess puzzle does not show how many captures will have in the next movement. It is difficult to identify all captures for one who is not advanced in the chess game. It is easy to identify if it is in graphical form. Here we represent a chess puzzle as a fuzzy graph. Moreover, identifying the number of possible targets using a fuzzy colouring approach.

A chess puzzle can be modelled as a fuzzy graph. Black and White pieces can be taken as vertices of the fuzzy graph. In a chess puzzle, the next turn will be either the Black piece’s side or the side of the white piece. Thus, the pieces in the same group cannot capture themselves. There is an edge between if one can capture the other after an ‘n’ number of movements through blank squares. Using the fuzzy colouring concept, this fuzzy graph model can find the number of possible targets of black pieces (or white pieces) based on which side the turn is located.

We assign the membership value of each vertex as one, edge membership values between two pieces are defined as follows. Assume the turn is for white pieces. For a white piece ‘u’ and a black piece ‘v’, μ (u, v) is defined as

μ ( u , v ) = min { 1 , no : of minimum movements to capture v by u through blank squares 3 } From the μ value, it is clear that if the μ (u, v) is less, then the chance of capturing ‘v’ by ‘u’ is high. When colouring the modelled fuzzy graph using fuzzy colouring, those vertices that obtain fuzzy colours are the possible targets of white pieces (assumed turn is for white pieces). That is, we identify the number of black pieces that white pieces can capture in one move. We explain this approach by considering a chess puzzle.

Figure 8 represents an 8×8 chess puzzle. Now the turn is for white. The problem is to identify possible targets of white using fuzzy colouring.

OPEN IN VIEWER

Fig. 8

8x8 chess puzzle.

Consider the fuzzy graph model in Fig. 8. The vertices are the white and black pieces, and two vertices u and v are adjacent if u can capture v after an ‘n’ number of movements through blank squares. There is no edge between two white pieces (or two black pieces). Here, we use the standard notation to represent the pieces. When referencing a piece, the abbreviation is always capitalized. The king is abbreviated by the letter ‘K’, the queen is abbreviated by the letter ‘Q’, the rook is abbreviated by the letter ‘R’, and the bishop is abbreviated by the letter ‘B’. The knight, a special case, is abbreviated by the letter ‘N’ since ‘K’ is already taken by the king. The pawn is the only piece that has no abbreviation. If a pawn is moved, then we see only the square’s name where the pawn moves. In Fig. 8, the black queen moved from d7 to f7. Now the turn is for white, and we aim to identify the no: of possible captures of white pieces.

Standard notations are used to represent the pieces and squares of the chess puzzle. Notations of the pieces (vertices) in Fig. 8 are given in Tables 1

and 2. Sigma values of each vertex are one. For vertices u in the white set and v in the black set, μ (u, v) is min { 1 , 1 3 (no: of minimum movements to capturev by u through blank squares)}

Note that White cannot capture white pieces. Therefore, adjacency is only possible with black pieces. Below, Fig. 9 represents the adjacency of B3 with vertex e5. The number of minimum movements to capture black pawn e5 by Bishop in e3 is 2 (it is represented in Fig. 9)

OPEN IN VIEWER

Fig. 9

Representation of minimum number of movements of B3 to capture e5.

Thus, μ ( B 3 , e 5 ) = min { 1 , 2 3 } = 0.67 , ( B 3 , e 5 ) is a strong edge

OPEN IN VIEWER

Fig. 10

Representation of minimum number of movements of B3 to capture Bd and b6.

Since B3 is in the dark square, it cannot capture the black pieces in white squares. Thus, there is no edge with them.

The number of minimum movements to capture black Bishop in d6 and pawn in b6 by B3 is 2 and 1, respectively (represented in Fig. 10).

Thus, μ ( B 3 , Bd ) = min { 1 , 2 3 } = 0.67 , ( B 3 , Bd ) is a strong edge μ ( B 3 , b 6 ) = min { 1 , 1 3 } = 0.34 , ( B 3 , b 6 ) is a weak edge

With one step, B3 can capture b6. Note that B3 can capture the pawn in c7 after capturing b6 in two steps, which is impossible by our definition. However, B3 can capture c7 after three steps through B3-g5-d8-c7. Thus, μ ( B 3 , c 7 ) = min { 1 , 3 3 } = 1 Similarly, we can find the other μ values; the edge membership values are given in the Table 3.

Now, this fuzzy graph is created with two basic colours: red and green. For white pieces, we can colour in red. Moreover, the black pieces get green colour, those who make strong edges with white pieces, whereas vertices that make weak edges with white pieces will get the colour fuzzy red. Note that the edges (Qe, e5), (B3, b6), and (Qe, h7) are weak edges, and the other edges are strong. The vertices e5, b6, and h7 obtain fuzzy red (see Fig. 11).

OPEN IN VIEWER

Fig. 11

Fuzzy graph representation of the chess puzzle in Fig. 8 and its fuzzy colouring.

Note that the μ values are 0.34, 0.67 and 1. The black vertices that obtain fuzzy colour always have an μ value of 0.34 with at least one adjacent white vertex. That is, these vertices can be captured by at least one white piece with one movement. Therefore, they are the possible captures of white turns. The number of possible captures in the white turn of the chess puzzle in Fig. 8 is 3.

Conclusion

In the resultant fuzzy graph of operations of a fuzzy graph, the fuzzy chromatic number of the graph is analysed. In addition, additional operations such as k ^th power, u- product, and strong edge product were introduced between two fuzzy graphs. The fuzzy chromatic number of resultant of the union of two fuzzy graphs, join and newly defined operations k ^th power, u- product and strong edge product are also defined. Using fuzzy colouring, the number of possible captures in a chess puzzle was determined. White pieces at the end of weak edges are possible targets of the opposing team, whereas black pieces at the end of strong edges are safe. The number of possible captures is equal to the number of vertices with a fuzzy colour. Using fuzzy colouring, we can determine the number of possible captures for each turn. Note that the getting fuzzy graph will vary with each turn. Fuzzy or edge colouring will likely be recommended in the future for determining the best move in a chess puzzle. Using edge colouring, one can extend this research work on newly defined operations to find its properties along with real-life applications.