On construction of fuzzy chromatic number of cartesian product of path and other fuzzy graphs

Abstract

We use the notion of fuzzy chromatic number (FCN) of fuzzy graphs based on fuzzy independent vertex sets introduced in 2015. Let ${\tilde{G}}_{1}$ be a path fuzzy graph and ${\tilde{G}}_{2}$ be any fuzzy graphs where their vertex sets are disjoint. Let $\tilde{G} = {\tilde{G}}_{1} □ {\tilde{G}}_{2}$ be a cartesian product of ${\tilde{G}}_{1}$ and ${\tilde{G}}_{2}$ . In this paper, we construct formula for FCN of ${\tilde{G}}_{1} □ {\tilde{G}}_{2}$ and verify connection between maximum of FCN of both fuzzy graphs and FCN of their cartesian product. Also, we create an algorithm to determine FCN of the cartesian product according to the properties obtained. The last two statements show novelties of the present work. Evaluation of the algorithm is presented in the experimental results.

Keywords

Fuzzy chromatic number cartesian product path fuzzy graph algorithm

1 Introduction

A graph was used to model many real problems where vertices represent objects and edges represent connection between two objects on a network ([1 , 11]). In real world, connection between two objects is uncertain. For example, a conflict between two traffic movements in traffic networks is an indeterminate phenomenon. Also, signal interferences between two transmitters in telecommunication networks are imprecise phenomena. Therefore, we need another type of graph that can model these phenomena. This is one of the reasons why fuzzy graph is needed. The research on fuzzy graph has developed rapidly. Recently, Poulik and Ghorai [20] have proposed detour g-interior nodes and detour g-boundary nodes in bipolar fuzzy graph with applications. Further, they also have investigated certain indices of graphs in bipolar fuzzy environment [21]. In [22], Poulik and Ghorai have established an updated version of definition and theorem in bipolar fuzzy graphs and demonstrated some numerical examples. Furthermore, Sahoo et al. [24] provided certain types of edge irregular intuitionistic fuzzy graphs. Also, they discussed covering and paired domination in intuitionistic fuzzy graphs in [25].

Kaufmann initiated a fuzzy graph with fuzzy edge set in 1973 [26]. Whereas, Rosenfeld introduced a fuzzy graph where fuzziness appears in both vertex and edge sets [26]. After that, many concepts in fuzzy graphs were generalized, such as dominating set, clique, and independent vertex set. For more concepts in fuzzy graphs, readers may refer to [4, 16], and [17]. Further, the concept of coloring of fuzzy graph was introduced by several researchers ([3 , 19]). However, some of the methods of fuzzy graph coloring still involved crisp chromatic number.

Papers related to generalization of chromatic number can be found in [3 , 19], and [27]. Munoz et al. [19] provided fuzzy chromatic number (FCN) of fuzzy graphs based on α-cut graphs coloring. Meanwhile, Bershtein and Bozhenuk ([3, 4]) defined FCN by means of maximal independent vertex sets. Keshavarz [12] gave an FCN of fuzzy graphs through incompatibility degrees of adjacent vertices. In 2015, we established FCN of fuzzy graphs based on fuzzy independent vertex sets [27] which is different to the works in [3, 4 and 19]. We also initiated a concept of an uncertain chromatic number by means of uncertainty theory in [28]. Recently, we have constructed FCN of join and union of fuzzy graphs ([29, 30]). In 2019, we have constructed FCN of cartesian product of path and complete fuzzy graphs and designed an algorithm ([31, 32]).

Cartesian product of fuzzy graphs has been used to model real problems, such as in the product of DNA structure [18], in computer science, geometry, algebra, number theory [23], also in combinatorial bayesian optimization [8]. Therefore, we are interested in investigating some problems related to cartesian product of fuzzy graphs. The problem to find FCN of cartesian product of any two fuzzy graphs has not been solved until now. Also, properties of FCN of the cartesian product have not been verified. We are interested to investigate FCN of the cartesian product of fuzzy graphs because the FCN is more suitable to handle indeterminate phenomena in real problems. Furthermore, the result in [32] is a general algorithm to find FCN of cartesian product of any fuzzy graphs based on FCN algorithm in [30] and the cartesian product concept. In other words, an algorithm to find FCN of cartesian product of path and other fuzzy graphs which is constructed based on the properties of FCN has not been created. In order to complete the work in [31] and [32], the aims of this research are to construct FCN of cartesian product of path and other fuzzy graphs, to investigate properties of the FCN, to develop an algorithm based on the properties obtained, and to verify ranking between FCN of the cartesian product ${\tilde{G}}_{1} □ {\tilde{G}}_{2}$ and FCN of ${\tilde{G}}_{1}$ and ${\tilde{G}}_{2}$ based on the concept of ranking between discrete fuzzy numbers.

This paper is organized as follows: Section 2 discusses basic theories needed to solve the problems. Construction of FCN of cartesian product of path and other fuzzy graphs is presented in Section 3. Moreover, an algorithm to determine FCN of the cartesian product is described in Section 3. Finally, conclusions are given in Section 4.

2 Theoretical background

In this section, we recall some basic concepts in fuzzy sets, fuzzy numbers, and fuzzy graphs which are needed to solve the problems.

Let X be a universal set (nonempty). A set ${(x, μ_{\tilde{B}} (x)) | x \in X}$ is called a fuzzy set $\tilde{B}$ on X with a membership function $μ_{\tilde{B}} : X \to [0, 1]$ [34]. We then call the classical sets as crisp sets. In this paper, we use the concepts of support, height, α-cut of fuzzy sets, and fuzzy numbers as in [15]. Further, the concept of discrete fuzzy number is cited from [6] and [33].

Given two discrete fuzzy numbers $\tilde{A}$ and $\tilde{B}$ . Let α ∈ [0, 1]. The α-cut sets of $\tilde{A}$ and $\tilde{B}$ are $A^{α} = {x_{1}^{α}, \dots, x_{m}^{α}}$ and $B^{α} = {y_{1}^{α}, \dots, y_{n}^{α}}$ , respectively. The supports of $\tilde{A}$ and $\tilde{B}$ are symbolized as S (A) and S (B), respectively. The sets S (A)⋁ S (B) = {z| max {min S (A) , min S (B)} ≤ z ≤ max {max S (A) , max S (B)} . It was defined in [6] that $P^{α} = {z \in S (A) ⋁ S (B) | max {x_{1}^{α}, y_{1}^{α}} \leq z \leq$ $max {x_{m}^{α}, y_{n}^{α}}} .$ The maximum of discrete fuzzy numbers $\tilde{A}$ and $\tilde{B}$ is defined as follows [7]: $max {\tilde{A}, \tilde{B}} = {(z, μ_{max {\tilde{A}, \tilde{B}}} (z))}$ with $μ_{max {\tilde{A}, \tilde{B}}} (z) = sup {α \in [0, 1] | z \in P^{α}} .$

Further, the set S (A) ⋀ S (B) = {z| min {min S (A) , min S (B)} ≤ z ≤ min {max S (A) , max S (B)}} . Given Q^α = {z ∈ S (A) $⋀ S (B) | min {x_{1}^{α}, y_{1}^{α}} \leq z \leq min {x_{m}^{α}, y_{n}^{α}}} .$ The mini-mum of $\tilde{A}$ and $\tilde{B}$ is as follows [7]: $min {\tilde{A}, \tilde{B}} = {(z, μ_{min {\tilde{A}, \tilde{B}}} (z))}$ with $μ_{min {\tilde{A}, \tilde{B}}} (z) = sup {α \in [0, 1] | z \in Q^{α}} .$

For any discrete fuzzy numbers $\tilde{A}$ and $\tilde{B}$ , $\tilde{B} ≽ \tilde{A} \Leftrightarrow max {\tilde{A}, \tilde{B}} = \tilde{B}$ . Otherwise, $\tilde{B} ⪯ \tilde{A} if and only if max {\tilde{A}, \tilde{B}} = \tilde{A}$ [7].

Given fuzzy graph ${\tilde{G}}_{1} (V_{1}, {\tilde{E}}_{1})$ where V₁ is a vertex set and ${\tilde{E}}_{1}$ is a fuzzy edge set with the membership function $μ_{{\tilde{E}}_{1}} : V_{1} \times V_{1} \to [0, 1]$ . We call ${\tilde{G}}_{1}$ as a fuzzy subgraph of $\tilde{G} (V, \tilde{E})$ if V₁ ⊆ V and ${\tilde{E}}_{1} \subseteq \tilde{E}$ .

Given fuzzy graphs ${\tilde{G}}_{1} (V_{1}, {\tilde{E}}_{1})$ and ${\tilde{G}}_{2} (V_{2}, {\tilde{E}}_{2})$ where V₁∩ V₂ = ∅, and ${\tilde{E}}_{1}$ , ${\tilde{E}}_{2}$ have membership functions μ₁ and μ₂, respectively. A cartesian product ${\tilde{G}}_{1} □ {\tilde{G}}_{2}$ is a graph consisting of a vertex set V = V₁ × V₂ and an edge set $\tilde{E}$ defined as ${(x, y_{1}) (x, y_{2}) | x \in V_{1}; y_{1} y_{2} \in {\tilde{E}}_{2}} \cup {(x_{1}, y) (x_{2}, y) | y \in V_{2}; x_{1} x_{2} \in {\tilde{E}}_{1}},$ with membership functions $μ_{\tilde{E}} ((x, y_{1}) (x, y_{2})) = μ_{2} (y_{1} y_{2})$ , and $μ_{\tilde{E}} ((x_{1}, y) (x_{2}, y)) = μ_{1} (x_{1} x_{2}) .$

Cioban [9] proposed a method to color fuzzy graphs which is based on a value δ. Given δ ∈ [0, 1]. A fuzzy independent vertex set (FIVS) $I nd \subseteq V$ is a subset of V that satisfies μ (x, y) ≤ δ, $\forall x, y \in I nd$ . It is also denoted as $I {nd}^{δ}$ . The k-coloring of $\tilde{G}$ is defined through partitioning vertex set V into δ-FIVS ${I {nd}_{1}^{δ}, I {nd}_{2}^{δ} \dots, I {nd}_{k}^{δ}}$ such that $I {nd}_{i} δ \cap I nd j^{δ} = \emptyset, \forall i \neq j$ and $I {nd}_{1}^{δ} \cup I {nd}_{2}^{δ} \dots \cup I {nd}_{k}^{δ} = V$ . The δ-chromatic number of $\tilde{G}$ is the minimum k needed in the k-coloring, symbolized as $χ^{δ} (\tilde{G})$ . Furthermore, the concept of fuzzy chromatic number (FCN) was given in [27]. The FCN of fuzzy graph $\tilde{G} (V, \tilde{E})$ with n vertices is a fuzzy set $\tilde{χ} (\tilde{G}) = {(k, L_{\tilde{χ}} (k)) | k = 1, 2, \dots, n}$ with $L_{\tilde{χ}} (k) = max {1 - δ | δ \in [0, 1], χ^{δ} (\tilde{G}) = k} .$ (1) The value $L_{\tilde{χ}} (k)$ in (1) denotes a membership degree of k in $\tilde{χ}$ .

3 Construction FCN of cartesian product of path and other fuzzy graphs and its algorithm

In this section, we discuss properties and algorithm of FCN of cartesian product of path and other fuzzy graphs. The properties are shown on two theorems. First theorem depicts construction of FCN of the cartesian product. On the second theorem, we give ranking between FCN of the two fuzzy graphs and their cartesian product. Following Theorem 1, we establish an algorithm (Table 2) in determining FCN of the cartesian product.

3.1 Properties of FCN of cartesian product of path and other fuzzy graphs

Theorem 1. Given path fuzzy graph ${\tilde{G}}_{1} (V_{1}, {\tilde{E}}_{1})$ and any fuzzy graphs ${\tilde{G}}_{2} (V_{2}, {\tilde{E}}_{2})$ with FCN ${\tilde{χ}}_{1}$ and ${\tilde{χ}}_{2}$ , respectively. Let |V₁| = n₁ and |V₂| = n₂. If $\tilde{G}$ is the cartesian product ${\tilde{G}}_{1} □ {\tilde{G}}_{2}$ , then FCN of $\tilde{G}$ is $\tilde{χ} (\tilde{G}) = {(k, L_{\tilde{χ}} (k))}$ , where $L_{\tilde{χ}} (k) = {\begin{matrix} min {L_{{\tilde{χ}}_{1}} (k), L_{{\tilde{χ}}_{2}} (k)}, if 1 \leq k < k^{'}; \\ k^{'} = min {1 \leq n^{'} \leq n_{2}, L_{{\tilde{χ}}_{2}} (n^{'}) = 1}; \\ 1, if k^{'} \leq k \leq n_{1} \times n_{2} . \end{matrix}$

Proof. Let V₁ = {u₁, u₂, …, u_{n
₁}} and V₂ = {v₁, v₂, …, v_{n
₂}}. Since ${\tilde{G}}_{1}$ is a path fuzzy graph, membership degree of edge μ (u_iu_i+1) >0 for each edge $u_{i} u_{i + 1} μ (u_{i} u_{i + 1}) \in {\tilde{E}}_{1}$ with 1 ≤ i ≤ n - 1. Hence, FCN of ${\tilde{G}}_{1}$ is ${\tilde{χ}}_{1} ({\tilde{G}}_{1}) = {(1, L_{{\tilde{χ}}_{1}} (1)), (2, 1), (3, 1), \dots, (n_{1}, 1)} .$ (2) We prove the theorem through mathematical induction on k.

For k = 1: let δ ∈ [0, 1]. Let μ_max1 = max {μ (u_iu_j) |u_i, u_j ∈ V₁} and μ_max2 = max {μ (v_iv_j) |v_i, v_j ∈ V₂}. It is obvious that $L_{{\tilde{χ}}_{1}} (1) = 1 - μ_{\max 1}$ and $L_{{\tilde{χ}}_{2}} (1) = 1 - μ_{\max 2} .$ Let δ_max = max {μ_max1, μ_max2}. Based on Equation (1), $L_{\tilde{χ}} (1) = max {1 - δ | χ^{δ} (\tilde{G}) = 1} = 1 - δ_{\max} = min {L_{{\tilde{χ}}_{1}} (1), L_{{\tilde{χ}}_{2}} (1)}$ and the theorem is true for k = 1.

Further, we assume that the theorem is fulfilled when k = r (1 < r < k′) with $k^{'} = min {1 \leq n^{'} \leq n_{2}, L_{{\tilde{χ}}_{2}} (n^{'}) = 1}$ . It means that $L_{\tilde{χ}} (r) = min {L_{{\tilde{χ}}_{1}} (r), L_{{\tilde{χ}}_{2}} (r)}$ . We will proof the theorem for k = r + 1.

If ${\tilde{G}}_{2}$ is a cycle fuzzy graph with even number of vertices, then FCN of the cartesian product $\tilde{G}$ has the number r = 2 with the degree $L_{\tilde{χ}} (r) = 1 = min {L_{{\tilde{χ}}_{1}} (r), L_{{\tilde{χ}}_{2}} (r)}$ . Otherwise, it is impossible that r = 2 in $\tilde{χ} (\tilde{G})$ has $L_{\tilde{χ}} (r) = 1$ . According to Equation (1), we have: $L_{\tilde{χ}} (r) = L_{{\tilde{χ}}_{2}} (r) = min {L_{{\tilde{χ}}_{1}} (r), L_{{\tilde{χ}}_{2}} (r)}$ Further, based on Equation (1): $L_{\tilde{χ}} (r) = max {1 - δ | χ^{δ} (\tilde{G}) = r} = L_{{\tilde{χ}}_{2}} (r) .$ To find the value δ such that $L_{\tilde{χ}} (r) = L_{{\tilde{χ}}_{2}} (r)$ , we verify all clique fuzzy subgraphs of ${\tilde{G}}_{2}$ with orders r + 1, namely $Q_{r + 1}^{1}, Q_{r + 1}^{2}, \dots, Q_{r + 1}^{m^{'}} .$ Let $δ_{r} = max {min {μ_{2} (Q_{r + 1}^{1})}, min {μ_{2} (Q_{r + 1}^{2})},$ $\dots, min {μ_{2} (Q_{r + 1}^{m^{'}})}} .$ It is obvious that $L_{\tilde{χ}} (r) = L_{{\tilde{χ}}_{2}} (r) = 1 - δ_{r}$ . By using the same way, we verify clique fuzzy subgraphs of ${\tilde{G}}_{2}$ with orders r + 2 to find $L_{\tilde{χ}} (r + 1)$ . Let $Q_{r + 2}^{1}, Q_{r + 2}^{2}, \dots, Q_{r + 2}^{l}$ be clique fuzzy subgraphs of ${\tilde{G}}_{2}$ with orders r + 2 that contain cliques $Q_{r + 1}^{1}, Q_{r + 1}^{2}, \dots, Q_{r + 1}^{m^{'}}$ with l < m′. Set $δ_{r + 1} = max {min {μ_{2} (Q_{r + 2}^{1})}, min {μ_{2} (Q_{r + 2}^{2})},$ $\dots, min {μ_{2} (Q_{r + 2}^{l})}}$ .

It is clear that $L_{{\tilde{χ}}_{2}} (r + 1) = 1 - δ_{r + 1}$ . Since ${\tilde{G}}_{1}$ is path fuzzy graph, $L_{{\tilde{χ}}_{1}} (r + 1) = 1$ for r > 1. Therefore, $L_{\tilde{χ}} (r + 1) = 1 - δ_{r + 1} = min {1, 1 - δ_{r + 1}} = min {L_{{\tilde{χ}}_{1}} (r + 1), L_{{\tilde{χ}}_{2}} (r + 1)}$

and the proof is complete. ■

Theorem 2. Given path fuzzy graph ${\tilde{G}}_{1} (V_{1}, {\tilde{E}}_{1})$ and any fuzzy graph ${\tilde{G}}_{2} (V_{2}, {\tilde{E}}_{2})$ with FCN ${\tilde{χ}}_{1}$ and ${\tilde{χ}}_{2}$ , respectively. Let n₁ be the number of vertices in ${\tilde{G}}_{1}$ and n₂ be the number of vertices in ${\tilde{G}}_{2}$ . If FCN of the cartesian product $\tilde{G} = {\tilde{G}}_{1} □ {\tilde{G}}_{2}$ is $\tilde{χ} = {(k, L_{\tilde{χ}} (k))}$ , then $\tilde{χ} ≽ max {\tilde{χ_{1}}, \tilde{χ_{2}}} .$ (3)

Proof. We know that ${\tilde{G}}_{1}$ is a path fuzzy graph. Hence, FCN of ${\tilde{G}}_{1}$ is shown in Equation (1). Whereas, ${\tilde{χ}}_{2} ({\tilde{G}}_{2}) = {(k, L_{\tilde{χ_{2}}} (k))}$ . We verify maximum of $\tilde{χ}, \tilde{χ_{1}}, \tilde{χ_{2}}$ based on the concept of maximum of discrete fuzzy numbers through α-cut sets as in [7]. Given α ∈ [0, 1], the α-cut sets of $\tilde{χ_{1}}$ and $\tilde{χ_{2}}$ are $χ_{1}^{α} = {l_{1}^{α}, \dots, l_{m}^{α}}$ and $χ_{2}^{α} = {k_{1}^{α}, \dots, k_{n}^{α}}$ , respectively.

The supports of ${\tilde{χ}}_{1}$ and ${\tilde{χ}}_{2}$ are presented as S (χ₁) and S (χ₂), respectively. We provide the set $\begin{matrix} S (χ_{1}) ⋁ S (χ_{2}) = & {z | max {min S (χ_{1}), min S (χ_{2})} \leq \\ z \leq max {max S (χ_{1}), max S (χ_{2})}} . \\ = {1, 2, 3, \dots, max {n_{1}, n_{2}}} . \end{matrix}$

In one hand, we can check the inequality (3) by comparing the maximum of $max {\tilde{χ_{1}}, \tilde{χ_{2}}}$ and $\tilde{χ}$ as follows: Let $P^{α} = {z \in S (χ_{1}) ⋁ S (χ_{2}) | max {l_{1}^{α}, k_{1}^{α}} \leq z \leq max {l_{m}^{α}, k_{n}^{α}}} .$ Let $α_{min}^{k} = min {L_{\tilde{χ_{1}}} (k), L_{\tilde{χ_{2}}} (k)}$ for k ≥ 1. It is visible that $\begin{matrix} χ_{1}^{α_{min}^{1}} = {1, 2, 3, \dots, n_{1}}; \\ χ_{1}^{α_{min}^{2}} = {2, 3, \dots, n_{1}}; \dots; \\ χ_{1}^{1} = {k \in {\tilde{χ}}_{1} | L_{{\tilde{χ}}_{1}} (k) = 1} = {l^{'}, \dots, n_{1}}, \\ l^{'} = min {1 \leq k \leq n_{1} | L_{{\tilde{χ}}_{1}} (k) = 1} . \\ χ_{2}^{α_{min}^{1}} = {1, 2, 3, \dots, n_{2}}; \\ χ_{2}^{α_{min}^{2}} = {2, 3, \dots, n_{2}}; \dots; \\ χ_{2}^{1} = {k^{'}, \dots, n_{2}}, \\ k^{'} = min {1 \leq k \leq n_{2} | L_{{\tilde{χ}}_{2}} (k) = 1} . \end{matrix}$ Based on Equation (2), we get l′ =2 ≤ k′. It means that max {l′, k′} = k′. Therefore, $\begin{matrix} P^{α_{min}^{1}} = {1, 2, 3, \dots, max {n_{1}, n_{2}}}; \\ P^{α_{min}^{2}} = {2, 3, \dots, max {n_{1}, n_{2}}}; \\ P^{α_{min}^{3}} = {3, \dots, max {n_{1}, n_{2}}}; \dots; \\ P^{1} = {k^{'}, \dots, max {n_{1}, n_{2}}} . \end{matrix}$

Thus, $max {{\tilde{χ}}_{1}, {\tilde{χ}}_{2}} = {(1, α_{min}^{1}), (2, α_{min}^{2}), (3, α_{min}^{3}), \dots,$ (k′, 1) , …, (max {n₁, n₂} , 1)} .

In addition, FCN of the cartesian product $\tilde{G}$ can be obtained through Theorem 1 as follows: $\tilde{χ} = {(1, α_{min}^{1}), (2, α_{min}^{2}), (3, α_{min}^{3}), \dots (k^{'}, 1), \dots, (n_{1} \times n_{2}, 1)}$ .

Further, we compare $max {{\tilde{χ}}_{1}, {\tilde{χ}}_{2}}$ and $\tilde{χ}$ . We obtain: $\begin{matrix} P^{α_{min}^{1}} = {1, 2, 3, \dots, n_{1} \times n_{2}}; \\ P^{α_{min}^{2}} = {2, 3, \dots, n_{1} \times n_{2}}; \\ P^{α_{min}^{3}} = {3, \dots, n_{1} \times n_{2}}; \dots; \\ P^{1} = {k^{'}, \dots, n_{1} \times n_{2}} . \end{matrix}$

Hence, $\begin{matrix} max {max {{\tilde{χ}}_{1}, {\tilde{χ}}_{2}}, \tilde{χ}} \\ = {(1, α_{min}^{1}), (2, α_{min}^{2}), (3, α_{min}^{3}), \dots, (k^{'}, 1), \dots, \\ (n_{1} \times n_{2}, 1)} = \tilde{χ} . \end{matrix}$

Thus, $\tilde{χ} ≽ max {\tilde{χ_{1}}, \tilde{χ_{2}}}$ .

In other hand, we can prove the inequality (3) by comparing the minimum of $max {\tilde{χ_{1}}, \tilde{χ_{2}}}$ and $\tilde{χ}$ as follows:

$\begin{matrix} S (max {\tilde{χ_{1}}, \tilde{χ_{2}}}) ⋀ S (χ) \\ = {z | min {min S (max {\tilde{χ_{1}}, \tilde{χ_{2}}}), min S (χ)} \leq z \leq \\ min {max S (max {\tilde{χ_{1}}, \tilde{χ_{2}}}), max S (χ)} . \\ = {1, 2, 3, \dots, max {n_{1}, n_{2}}} . \end{matrix}$

It is clear that $S (max {\tilde{χ_{1}}, \tilde{χ_{2}}}) = {1, 2, 3, \dots, max {n_{1}, n_{2}}}$ and S (χ) = {1, 2, …, n₁ × n₂}. Let $Q^{α} = {z \in S (max {\tilde{χ_{1}}, \tilde{χ_{2}}}) ⋀ S (χ) | min {l_{1}^{α}, k_{1}^{α}}$ $\leq z \leq min {l_{m}^{α}, k_{n}^{α}}} .$ By the same way, we get $\begin{matrix} Q^{α_{min}^{1}} = {1, 2, 3, \dots, max {n_{1}, n_{2}}}; \\ Q^{α_{min}^{2}} = {2, 3, \dots, max {n_{1}, n_{2}}}; \\ Q^{α_{min}^{3}} = {3, \dots, max {n_{1}, n_{2}}}; \dots; \\ Q^{1} = {k^{'}, \dots, max {n_{1}, n_{2}}} . \end{matrix}$

Thus, $\begin{matrix} min {max {\tilde{χ_{1}}, \tilde{χ_{2}}}, χ} \\ = {(1, α_{min}^{1}), (2, α_{min}^{2}), (3, α_{min}^{3}), \dots, (k^{'}, 1), \\ \dots, (max {n_{1}, n_{2}}, 1)} \\ = max {\tilde{χ_{1}}, \tilde{χ_{2}}} \end{matrix}$

We also have $\tilde{χ} ≽ max {\tilde{χ_{1}}, \tilde{χ_{2}}}$ and the theorem is proved. ■

Furhermore, a remark related to Theorem 1 and Theorem 2 is given as follows.

Remark 1. Given ${\tilde{G}}_{1}, {\tilde{G}}_{2}$ with the underlying crisp graphs $G_{1}^{*}, G_{2}^{*}$ , respectively and their chromatic numbers are $χ_{1}^{*}, χ_{2}^{*}$ . When the degree $L_{\tilde{χ}} (k) = 0$ for $1 \leq k < max {χ_{1}^{*}, χ_{2}^{*}}$ and $L_{\tilde{χ}} (k) = 1$ for $k = max {χ_{1}^{*}, χ_{2}^{*}}$ , then FCN of the cartesian product $\tilde{χ} ({\tilde{G}}_{1} □ {\tilde{G}}_{2})$ becomes chromatic number of the cartesian product of crisp graphs $χ^{*} (G_{1}^{*} □ G_{2}^{*})$ . In other words, the equality $χ = max {χ_{1}^{*}, χ_{2}^{*}}$ is fulfilled in the chromatic number of cartesian product of crisp graphs, but we only get the inequality in the FCN of the cartesian product.

An illustration of Theorem 1 is given inExample 1.

Example 1. Given two fuzzy graphs ${\tilde{G}}_{1} (V_{1}, {\tilde{E}}_{1})$ and ${\tilde{G}}_{2} (V_{2}, {\tilde{E}}_{2})$ in Fig. 1 and the cartesian product is shown in Fig. 2.

Fig. 1

Path fuzzy graph ${\tilde{G}}_{1}$ and fuzzy graph ${\tilde{G}}_{2}$ .

Fig. 2

The cartesian product ${\tilde{G}}_{1} □ {\tilde{G}}_{2}$ of fuzzy graphs in Fig. 1.

FCN of fuzzy graphs ${\tilde{G}}_{1}$ and ${\tilde{G}}_{2}$ are shown in Table 1 (column 3 of rows 1 and 2). Meanwhile, FCN of the cartesian product that determined through Theorem 1 is also presented in Table 1 (column 3 of row 3).

Table 1

FCN of ${\tilde{G}}_{1}$ , ${\tilde{G}}_{2}$ , and the cartesian product ${\tilde{G}}_{1} □ {\tilde{G}}_{2}$ of fuzzy graphs in Fig. 1

No.	Fuzzy graph	FCN
1	${\tilde{G}}_{1}$	${\tilde{χ}}_{1} ({\tilde{G}}_{1}) = {(1, 0.3), (2, 1), (3, 1)}$
2	${\tilde{G}}_{2}$	${\tilde{χ}}_{2} ({\tilde{G}}_{2}) = {(1, 0.1), (2, 0.4), (3, 0.8),$
		(4, 0.9) , (5, 1) , (6, 1)}
3	$\tilde{G} = {\tilde{G}}_{1} □ {\tilde{G}}_{2}$	$\tilde{χ} (\tilde{G}) = {(1, 0.1), (2, 0.4), (3, 0.8),$
		(4, 0.9) , (5, 1) , (6, 1) ,
		(7, 1) , …, (18, 1)} .

Further, we compare FCN ${\tilde{χ}}_{1}, {\tilde{χ}}_{2},$ and $\tilde{χ}$ by using ranking of discrete fuzzy numbers through α-cut which is proved in Theorem 2. Based on Table 1: $α_{min}^{1} = 0.1, α_{min}^{2} = 0.4, α_{min}^{3} = 0.8, α_{min}^{4} = 0.9,$ $α_{min}^{1} = 1$ . Further, $S ({\tilde{χ}}_{1}) ⋁ S ({\tilde{χ}}_{2}) = {1, 2, 3, \dots, 6},$ $\begin{matrix} P^{0.1} = {1, 2, 3, 4, 5, 6}; P^{0.3} = {2, 3, 4, 5, 6}; \\ P^{0.4} = {2, 3, 4, 5, 6}; P^{0.8} = {3, 4, 5, 6}; \\ P^{0.9} = {4, 5, 6}; P^{1} = {5, 6} . \end{matrix}$

Therefore, $max {{\tilde{χ}}_{1}, {\tilde{χ}}_{2}} = {(1, 0.1), (2, 0.4), (3, 0.8), (4, 0.9), (5, 1), (6, 1)} = {\tilde{χ}}_{2}$ .

Moreover, we compare $max {{\tilde{χ}}_{1}, {\tilde{χ}}_{2}}$ and $\tilde{χ}$ as follows: $\begin{matrix} S (max {{\tilde{χ}}_{1}, {\tilde{χ}}_{2}}) ⋁ S (\tilde{χ}) = {1, 2, 3, \dots, 18} . \\ P^{0.1} = {1, 2, 3, \dots, 18}; P^{0.3} = {2, 3, \dots, 18}; \\ P^{0.4} = {2, 3, \dots, 18}; P^{0.8} = {3, 4, \dots, 18}; \\ P^{0.9} = {4, 5, \dots, 18}; P^{1} = {5, 6, \dots, 18} . \end{matrix}$

We get $max {max {{\tilde{χ}}_{1}, {\tilde{χ}}_{2}}, \tilde{χ}} = {(1, 0.1), (2, 0.4), (3, 0.8), (4, 0.9), (5, 1), (6, 1), (7, 1), \dots, (18, 1)} = \tilde{χ} .$ Thus, $\tilde{χ} ≽ max {\tilde{χ_{1}}, \tilde{χ_{2}}}$ .

We can also get FCN of the cartesian product $\tilde{χ} (\tilde{G})$ in Table 1 (row 3, column 3) by using an algorithm discussed in Section 3.2.

3.2 A proposed algorithm to find FCN of cartesian product of path and other fuzzy graphs

An algorithm to find FCN of cartesian product of path and other fuzzy graphs is designed as shown in Table 2. Step 1 until Step 6 (in Table 2) are inputing vertices and edges of fuzzy graphs ${\tilde{G}}_{1}, {\tilde{G}}_{2}$ and $\tilde{G} = {\tilde{G}}_{1} □ {\tilde{G}}_{2}$ . Steps 7–8 are finding fuzzy chromatic number of ${\tilde{G}}_{1}, {\tilde{G}}_{2}$ by using FCN function in Matlab [30]. Furthermore, Step 9 until Step 16 are calculating degrees of k in FCN of the cartesian product $\tilde{χ} = {(k, L_{\tilde{χ}} (k))}$ based on Theorem 1. Finally, Step 17 and Step 18 are to print the FCN.

Table 2
Algorithm to find FCN of cartesian product of path and other fuzzy graphs

Steps Commands

1 Input E1, μ1 % edges in ${\tilde{G}}_{1}$ and its

membership function

2 Input E2, μ2 % edges in ${\tilde{G}}_{2}$ and its

membership function

3 V₁ = unique(E1);V₂ = unique(E2) % define vertex sets

of ${\tilde{G}}_{1}$ and ${\tilde{G}}_{2}$

4 set n1 = numel (V₁) % cardinality of V₁

5 set n2 = numel (V₂) % cardinality of V₂

6 set n = n1 . n2 % cardinality of

V₁ × V₂

7 set [k1 L1] = FCN (E1, μ1) % find FCN of ${\tilde{G}}_{1}$

8 set [k2 L2] = FCN (E2, μ2) % find FCN of ${\tilde{G}}_{2}$

9 set L(1) = min(L1 (1) , L2 (1)) % calculate degree

of k = 1 in FCN $\tilde{χ}$

10 if k′ = min k ∈ {1, 2, …, n₂} % calculate degree of

k > 1 in FCN $\tilde{χ}$

11 for j=1 to k′ - 1

12 L(j) = min(L1 (j) , L2 (j))

13 end

14 else

15 L(j) = 1

16 end

17 set k = 1 : n

18 Print $\tilde{χ} =$ [k L] % display FCN of

${\tilde{G}}_{1} □ {\tilde{G}}_{2}$

Steps	Commands
1	Input E1, μ1	% edges in ${\tilde{G}}_{1}$ and its
		membership function
2	Input E2, μ2	% edges in ${\tilde{G}}_{2}$ and its
		membership function
3	V₁ = unique(E1);V₂ = unique(E2)	% define vertex sets
		of ${\tilde{G}}_{1}$ and ${\tilde{G}}_{2}$
4	set n1 = numel (V₁)	% cardinality of V₁
5	set n2 = numel (V₂)	% cardinality of V₂
6	set n = n1 . n2	% cardinality of
		V₁ × V₂
7	set [k1 L1] = FCN (E1, μ1)	% find FCN of ${\tilde{G}}_{1}$
8	set [k2 L2] = FCN (E2, μ2)	% find FCN of ${\tilde{G}}_{2}$
9	set L(1) = min(L1 (1) , L2 (1))	% calculate degree
		of k = 1 in FCN $\tilde{χ}$
10	if k′ = min k ∈ {1, 2, …, n₂}	% calculate degree of
		k > 1 in FCN $\tilde{χ}$
11	for j=1 to k′ - 1
12	L(j) = min(L1 (j) , L2 (j))
13	end
14	else
15	L(j) = 1
16	end
17	set k = 1 : n
18	Print $\tilde{χ} =$ [k L]	% display FCN of
		${\tilde{G}}_{1} □ {\tilde{G}}_{2}$

The algorithm has been evaluated on many cartesian product of path and other fuzzy graphs. In the next section, we present one of the experimental results related to the algorithm.

3.3 Experimental results

Let us consider path fuzzy graph ${\tilde{G}}_{1}$ , fuzzy graph ${\tilde{G}}_{2}$ in Fig. 1, and the cartesian product ${\tilde{G}}_{1} □ {\tilde{G}}_{2}$ is depicted in Fig. 2. FCN of ${\tilde{G}}_{1}$ , ${\tilde{G}}_{2}$ , and FCN of the cartesian product ${\tilde{G}}_{1} □ {\tilde{G}}_{2}$ are presented in Table 1. Whereas, the cartesian product obtained by computation using algorithm in [32] is presented in Fig. 3. FCN of the cartesian product in Table 1 (row 3) which is obtained from the proposed algorithm and the algorithm in [32] are displayed in Figs. 4 and 5, respectively.

Fig. 3

The cartesian product $\tilde{G} = {\tilde{G}}_{1} □ {\tilde{G}}_{2}$ in Fig. 2 represented by Matlab.

Fig. 4

Output of finding FCN of the cartesian product in Fig. 2 by the proposed algorithm.

Fig. 5

Output of finding FCN of the cartesian product in Fig. 2 by the general algorithm in [32].

Representation of FCN of ${\tilde{G}}_{1} □ {\tilde{G}}_{2}$ in Fig. 2 by using the proposed algorithm is given in Fig. 31. The algorithm is evaluated using Matlab R2016a. The average running time for finding FCN of the cartesian product through the proposed algorithm is 0.80978 seconds (Fig. 31). When we determine FCN of the cartesian product by means of general algorithm in [32], we get average running time 48.5936 seconds as shown in Fig. 32. The inputs to be proceed in the proposed algorithm are the edge sets $E_{1}^{*}, E_{2}^{*}$ with the cardinality m₁, m₂, respectively, and the sets of degree of membership of edges μ₁, μ₂. Whilst, the edge set to be proceed in the previous algorithm [32] has the cardinality m₁ × |V₂| + m₂ × |V₁|. Therefore, the size of inputs in the proposed algorithm (in Table 2) is smaller than the size of inputs in the previous algorithm [32]. Finally, the proposed algorithm always give less average running time compared with the general algorithm in [32].

4 Conclusions

We have constructed fuzzy chromatic number (FCN) of cartesian product of path and other fuzzy graphs in a theorem. Also, we have compared FCN of both fuzzy graphs and their cartesian product through the maximum concept of discrete fuzzy numbers. We show lower bound of FCN of the cartesian product in a theorem. Further, we have given the algorithm of constructing FCN of the cartesian product and the evaluation of the algorithm is shown in the experimental results. In upcoming research, we will construct FCN of cartesian product of any two fuzzy graph, examine the properties on it, design an algorithm, and verify complexity of the algorithm. Also, we will investigate FCN of strong product of fuzzy graphs, verify properties of the FCN, create an algorithm to find it, and show itcomplexity.

Footnotes

Acknowledgments

Authors thanks for assistance or encouragement from Nurhaida (n.nurhaida@unipa.ac.id) who gave fuzzy chromatic function in Matlab R2016a. Also, authors thanks to reviewers for their valuable comments.

References

Angelini

, Bekos

M.A.

, De Luca

, Didimo

, Kaufmann

, Kobourov

, Montecchiani

, Raftopoulou

C.N.

, Roselli

and Symvonis

, Vertex coloring with defects, Journal of Graph Algorithms and Applications 21(3) (2017), 313–340.

Appel

, Applications of graph theory in computer science an overview, International Journal of Engineering Science and Technology 2(9) (2010), 4610–4621.

Bershtein

L.S.

and Bozhenuk

A.V.

, A color problem for fuzzy graphs, in: Lecture Notes in Computer Science (LNCS2206), Springer, Berlin-Heidelberg, 2001, 500–505.

Bershtein

L.S.

and Bozhenuk

A.V.

, Fuzzy graphs and fuzzy hypergraphs, in: Encyclopedia of Artificial Intelligence, IGI Global, Hershey-USA, 2009, 704–709.

Brandes

and Wagner

, Using graph layout to visualize train interconnection data, Journal of Graph Algorithms and Applications 4(3) (2000), 135–155.

Casasnovas

and Riera

J.V.

, On the addition of discrete fuzzy numbers, WSEAS Transactions on Mathematics, 5(5) (2006), 549–554.

Casasnovas

and Riera

J.V.

, Lattice properties of discrete fuzzy numbers under extended min and max, in: Proceedings of IFSA-EUSFLAT, 2009, 647–652.

Changyong

Oh.

, Tomczak

J.M.

, Gavves

and Welling

, Combinatorial Bayesian Optimization using the Graph Cartesian Product, presented in: 33rd Conference on Neural Information Processing Systems (NeurIPS), Vancouver-Canada, 2019.

Cioban

, On independent sets of vertices in graphs, Studia Univ.Babes-Bolyai Informatica LII(1) (2007), 97–100.

10.

Eslahchi

and Onagh

B.N.

, Vertex-strength of fuzzy graphs, International Journal of Mathematics and Mathematical Sciences, 2006 (2006), 1–9.

11.

Kashyop

M.J.

, Nagayama

and Sadakane

, Faster algorithms for shortest path and network flow based on graph decomposition, Journal of Graph Algorithms and Applications 23(5) (2019), 781–813.

12.

Keshavarz

, Vertex-coloring of fuzzy graphs: a new approach, Journal of Intelligent & Fuzzy Systems 30(2) (2016), 883–893.

13.

Kishore

and Sunitha

M.S.

, Chromatic number of fuzzy graphs, Annal of Fuzzy Mathematics and Informatics 7(4) (2014), 543–551.

14.

Kishore

and Sunitha

M.S.

, Strong chromatic number of fuzzy graphs, Annals of Pure and Applied Mathematics 7 (2) (2014), 52–60.

15.

Klir

G.J.

and Yuan

, Fuzzy Sets and Fuzzy Logic, Theory and Applications, Prentice Hall P.T.R., 1995.

16.

Mathew

and Sunitha

M.S.

, Fuzzy graphs: basics, concepts and applications, Lap Lambert Academic Publishing, 2012.

17.

Mathew

, Mordeson

J.N.

and Malik.

D.S.

, Fuzzy Graph Theory, Springer Nature Switzerland AG, 2018.

18.

Mishra

S.N.

and Pal

, Minimum cycle bases of products of fuzzy graphs, An international journal of advanced computer technology 3(11) (2014), 1337–1342.

19.

Muñoz

, Ortuño

M.T.

, Ramírez

and Yáñez

, Coloring fuzzy graphs, Omega: The Journal of Management Science 33(3) (2005), 211–221.

20.

Poulik

and Ghorai

, Detour g-interior nodes and detour g-boundary nodes in bipolar fuzzy graph with applications, Hacettepe Journal of Mathematics & Statistics, doi: 10.15672/HJMS.2019.666, (2019), 1–14.

21.

Poulik

and Ghorai

, Certain indices of graphs under bipolar fuzzy environment with applications, Soft Computing, doi:10.1007/s00500-019-04265-z, (2019), 1–13.

22.

Poulik

and Ghorai

, Note on bipolar fuzzy graphs with applications, Knowledge-Based Systems, doi: 10.1016/j.knosys.2019.105315, (2019),1–5.

23.

Rashmanlou

, Pal

, Borzooei

R.A.

, Mofidnakhaei

and Sarkar

, Product of interval-valued fuzzy graphs and degree, Journal of Intelligent & Fuzzy Systems 35(6) (2018), 6443–6451.

24.

Sahoo

and Pal

, Certain types of edge irregular intuitionistic fuzzy graphs, Journal of Intelligent and Fuzzy Systems 34(1) (2018), 295–305.

25.

Sahoo

, Pal

, Rashmanlou

and Borzooei

R.A.

, Covering and paired domination in intuitionistic fuzzy graphs, Journal of Intelligent and Fuzzy Systems 33(6) (2017), 4007–4015.

26.

Rosenfeld

, Fuzzy graphs, in: Fuzzy sets and their applications to cognitive and decision processes, edited by L.A Zadeh, K.S. Fu and M. Shimura (Eds.), Academic Press, 1975, 77–95.

27.

Rosyida

, Widodo , Indrati

Ch.R.

and Sugeng

K.A.

, A new approach for determining fuzzy chromatic number of fuzzy graph, Journal of Intelligent and Fuzzy Systems 28(5) (2015), 2331–2341.

28.

Rosyida

, Peng

, Chen Widodo

, Indrati

Ch. R.

and Sugeng

K.A.

, An uncertain chromatic number of an uncertain graph based on α-cut coloring, Fuzzy Optimization and Decision Making 17(1) (2018), 103–123.

29.

Rosyida

, Widodo , Indrati

Ch. R.

and Indriati

, On fuzzy chromatic number of join of fuzzy graphs with an application, 2018 International Symposium on Advanced Intelligent Informatics (SAIN), 2018, 84–89.

30.

Rosyida

, Widodo , Indrati

Ch. R.

, Indriati

and Nurhaida , Fuzzy chromatic number of union of fuzzy graphs: an algorithm, properties and its application, Fuzzy Sets and Systems, 384 (2020), 115–131.

31.

Rosyida

, Widodo , Indrati

Ch. R.

and Indriati

, On fuzzy chromatic number of cartesian product of some fuzzy graphs and its application, Advances and Applications in Discrete Mathematics 20(2) (2019), 237–252.

32.

Rosyida

, Algorithms to determine fuzzy chromatic number of cartesian product and join of fuzzy graphs, Journal of Physics: Conference Series, 1489, 012005 (2020), 1–10.

33.

Wang

, Zhang

and Cui

, The discrete fuzzy numbers on a fixed set with finite support set, in: 2008 IEEE International Conference on Cybernetics and Intelligent Systems (CIS), 2008, 812–817.

34.

Zadeh

L.A.

, Fuzzy sets, Information and Control 33 (1965), 338–353.