Fuzzy incidence coloring on cartesian product of some fuzzy incidence graphs

1Introduction

A graph is a simple model relation that represents information between things skillfully. Objects and relationships are represented by vertices and edges. There is frequently uncertainty in the items or their relationships, or between both objects and their relationships, while describing a graph. Fuzzy graph models are well suited in this scenario. Mordeson et al. [10] introduced various fuzzy graph operations that can be used to generate new graphs from two existing graphs, such as union, join, cartesian product, and composition. Shovan Dogra [23] presented various fuzzy graph products to identify the degree of vertices, including modular, homomorphic, box dot, and star fuzzy graph products. Talal AL-Hawary [26] proposed three new operations: direct product, semi-strong product, and strong product for fuzzy graphs to be a complete fuzzy graph. Ghorai et al. [15] developed detour G-interior and detour G-boundary nodes with applications in a bipolar fuzzy network. In a bipolar fuzzy environment, they have also investigated a few graph indices [14]. The definition and theory of bipolar fuzzy graphs were revised by Ghorai et al. [16], and they also provided some numerical examples.

A FIG is a new approach to the degree to which an edge and a vertex incident were defined by Dinesh [5, 6]. FIGs, have long been acknowledged as an effective and well-organized tool for capturing and resolving a wide range of real-world scenarios involving ambiguous data and information. Because of the importance of unpredictability and nonspecific information in real-world problems that are usually uncertain, it is highly difficult for an expert to describe those difficulties using a fuzzy graph. As a result, establishing a FIG, on which fuzzy graphs may not produce appropriate results, can be utilized to address the uncertainty associated with any unpredictable and generic information of any real-world problem. Later, Sunil Mathew et al. [24] presented FIG connectivity principles, which are useful in interconnection networks with impacted flows. Because most interconnection networks do not follow the crisp rule, fuzzy graph theory can be applied to improve performance.

One of the most important challenges in combinatorial optimization is graph coloring, which is widely used to promote conflict resolution or the optimal division of mutually exclusive events. Many practical problems can be represented as coloring problems. Any graph can be usually related to two types of coloring namely, vertex coloring and edge coloring. Vertex coloring is a function that gives distinct colors to adjacent vertices. Edge coloring is a function that assigns distinct colors to the edges so that the incident edges are colored differently. Many researchers have experimented with some additional graph colorings like, centre coloring, fractional coloring, dynamic coloring, harmonic coloration, rainbow coloring, incidence coloring, and so on. Graph coloring is used in picture segmentation, image capture, data mining, scheduling, allocation, networking, and other real-time applications.

Any network that focuses on both data at the same time is subjected to incidence coloring. Constructing a wireless network in which a group of transceivers is connected in space communication is one of the major challenges in the frequency assignment problem. Each transceiver can send and receive data at the same time, and nearby transceivers with different frequencies avoid broadcast conflicts. As a result, the incidence coloring of graphs to be used to characterize the model such that neighborly incidences are assigned different colors. The incidence chromatic number is the least number of independent incidence sets, and incidence coloring separates the entire graph into disjoint separate incidence sets. Richard et al. [17] demonstrated incidence coloring on graphs such as trees, full graphs, and complete bipartite graphs, and they hypothesized that every graph G could be incidence colored with Δ + 2 colors. Cheng et al. [4] researched incidence coloring techniques for square meshes, hexagonal meshes, and honeycomb meshes with a minimum color requirement of Δ + 1. The chromatic number on some standard products of graphs with some applications of product colorings was introduced by Sandi Klavzar [22]. Incidence coloring on the cartesian product of some special classes of graphs was extensively investigated by Alexander et al. [1]. Petr Gregor et al. [13] introduced some sufficient properties of the two-factor graphs of a cartesian product graph which admits an incidence coloring with at most Δ + 2 colors.

Fuzzy coloring is used to deal with uncertainties such as vagueness and ambiguity in coloring situations. Because there may be a variation in coloring numbers between crisp and fuzzy graphs where crisp graph coloring may not yield appropriate results in the situation of uncertainty. Fuzzy coloring is created to color political maps as well as a variety of real-time scenarios like traffic light systems, immigration, work scheduling, image classification, and network communications. The process of coloring the fuzzy graphs was implemented by Munoz et al. [12]. Anjaly Kishore et al. [2] defined the chromatic number of fuzzy graphs and the chromatic number of threshold graphs to make the coloring of the fuzzy graph simple. The vertex coloring function uses the α-cut of a fuzzy graph to color all of the graph’s vertices and the method of getting the graph chromatic number was proposed by Arindam Dey et al. [3]. The edge coloring of fuzzy graphs was introduced by Rupkumar Mahapatra et al. [21] in which the chromatic index and the strong chromatic index with related attributes were examined. Furthermore, the edge coloring of fuzzy graphs has been more effectively used to solve the issues in the job-oriented websites and traffic light. Madhumangal Pal et al. [9] addressed fresh ideas for coloring fuzzy graphs, focusing mostly on vertex and edge coloring and illuminating their discussion with examples. Additionally, he introduced a fuzzy fractional chromatic number and proposed a new technique for fuzzy fractional coloring of a fuzzy graph. He studied several fuzzy graph types and provided useful examples. The representation of ecological problems, social networks, telecommunications systems, link prediction in fuzzy social networks, manufacturing industry competition, bus network patrolling, image contraction, cell phone tower installation, traffic signaling, job selection, etc. are just a few examples of real-world applications that are illustrated as fuzzy graphs.

Rosyida et al. [18] created a novel method by taking the FCN of the cartesian product of complete fuzzy graphs and path.The Fuzzy Chromatic Number (FCN) of the cartesian product of two fuzzy graphs was developed by Rosyida et al. [19, 20], and a relationship was found between the maximum FCN of two fuzzy graphs and the FCN of the cartesian product of those two fuzzy graphs. Additionally, in accordance with the characteristics revealed by the testing results, he created an algorithm to compute the cartesian product FCN. In everyday life, a variety of instances involving human loss may occur. In these cases, preserving human lives as well as preventing such events is equally important. Although these issues can be represented as graphs and solved via fuzzy coloring, it is valid for any one criteria. To address such issues, a new FIC with a quick turnaround time has been proposed. Some specific results on chromatic FIs were studied by Liu Xikui et al. [8]. We provided a new method based on FI such that vehicle waiting times were minimized to reduce the number of accidents and traffic jams as well as bounds for many FIGs using FIC [27].

2Preliminaries

Basic definitions of incidence coloring, FIC, and cartesian product of fuzzy graphs are found in this section.

Definition: 2.1 [17]. Let G = (V, E) be a multigraph of order n and of size m. Let I = {(v, e) : v ∈ V, e ∈ E, v is incident with e} be the set of incidences of G. We say that two incidences (v, e) and (w, f) are neighborly (adjacent) provided one of the following holds:

The configurations associated with (i)–(iii) are pictured in Fig. 2.1.

Fig. 2.1

Incidence pairs.

We define an incidence coloring of G to be a coloring of its incidences in which neighborly incidences are assigned different colors. The incidence coloring number of G, denoted by I (G), is the smallest number of colors in an incidence coloring.

Definition 2.2 [11]. Let (V, E) be a graph. Then G = (V, E, I) is called an incidence graph, where I ⊆ V × E. We note that if V ={ u, v } , E = { uv } and I ={ (v, uv) }, then (V, E, I) is an incidence graph even though (u, uv) ∉ I.

Definition 2.3 [11]. Let G = (V, E, I) be an incidence graph. If (u, vw) ∈ I, then (u, vw) is called an incidence pair or simply a pair. If (u, uv) , (v, uv) , (v, vw) , (w, vw) ∈ I, then uv and vw are called adjacent edges.

Definition 2.4 [5]. Let G = (V, E) be a graph and σ be a fuzzy subset of V and μ be a fuzzy subset of E (E ⊆ V × V). Let ψ be a fuzzy subset of V × E. If ψ (v, e) ⩽ σ (v) ∧ μ (e) for all v ∈ V and e ∈ E, then ψ is called a Fuzzy Incidence (FI) of G.

Definition 2.5 [6]. Let G = (V, E) be a graph and (σ, μ) be a fuzzy subgraph of G. If ψ is a Fuzzy Incidence of G, then G˜=(σ,μ,ψ) is called a Fuzzy Incidence Graph (FIG) of G.

Definition 2.6 [27]. An incidence coloring of Fuzzy Incidence Graph G˜ can be defined as a function F_c : ψ (G) → N such that F_C [ψ (v, e)] ≠ F_C [ψ (u, f)] for any Fuzzy Incidences ψ (v, e) & ψ (u, f) that are adjacent. This implies that an incidence coloring assigns distinct colors to its adjacent Fuzzy Incidences.

Definition 2.7 [27]. Let G˜=(σ,μ,ψ) be a Fuzzy Incidence Graph. Let C ={ φ_i ∈ ψ (σ × μ) : 1 ⩽ i ⩽ k }. Let k ∈N

That C is said to be k- Fuzzy Incidence Coloring (FIC).

Definition 2.8 [27]. The minimum number of colors needed for an incidence coloring of a fuzzy graph is known as Fuzzy Incidence Chromatic Number (FICN) or Fuzzy Incidence Coloring Number of G˜ and denoted by χψ(G˜) .

Definition 2.9 [10]. Let G₁ (σ₁, μ₁) and G₂ (σ₂, μ₂) be two fuzzy graphs with underlying vertex sets V₁ and V₂ and edge sets E₁ and E₂ respectively. Then cartesian product of G₁ and G₂ is pair of functions (σ₁ × σ₂, μ₁ × μ₂) with underlying vertex set V = V₁× V₂ = { (u₁, v₁) ; u₁∈V₁ and v₁∈V₂ }, and underlying edge set E = E₁× E₂ = { (u₁, v₁) (u₂, v₂) ; u₁ = u₂, (v₁, v₂) ∈E₂ or (u₁, u₂) ∈E₁, v₁ = v₂ } with

3Fuzzy Incidence Coloring Number on cartesian product graphs

The FICN on the cartesian product of some FIGs such as Pm˜×Pn˜,Pm˜×Cn˜,Pm˜×Kn,˜Cm˜×Cn˜,Cm˜×Kn˜,Km˜×Kn˜ are provided in this section.

Definition: 3.1. Let G1˜(σ1,μ1,ψ1) and G2˜(σ2,μ2,ψ2) are two FIGs with V₁ and V₂ as vertex sets, E₁ and E₂ as edge sets, Ψ₁ and Ψ₂ as Fuzzy Incidence pair sets respectively. The cartesian product of G1˜ and G2˜ is a function of (σ₁ × σ₂, μ₁ × μ₂, ψ₁ × ψ₂) with vertex set V = V₁× V₂ = { (v₁, t₁) ; v₁ɛV₁ and t₁ɛV₂ }, edge set E = E₁ × E₂ = {(v₁, t₁) (v₂, t₂) ; v₁ = v₂, (t₁, t₂) ɛE₂or (v₁, v₂) ɛ E₁, t₁ = t₂}, incidence pair set Ψ = Ψ₁ × Ψ₂ = { [(v₁, t₁) , (v₁, t₁) (v₂, t₂)] ; (v₁, t₁) ɛV₁ × V₂ and (v₁, t₁) (v₂, t₂) ɛE₁× E₂ }.

and whose fuzzy subsets σ₁ × σ₂ofV, μ₁ × μ₂ofE and ψ₁ × ψ₂ofΨ must defined as follows

Then the Fuzzy Incidence Graph (G1˜×G2˜)(σ1×σ2,μ1×μ2,ψ1×ψ2) is said to be the cartesian product of G1˜(σ1,μ1,ψ1) and G2˜(σ2,μ2,ψ2) . ■

An example for the Definition 3.1 is illustrated below.

Example 3.1. Let P2˜ be the FIP with 2 vertices whose degree 2 and C3˜ be the Fuzzy Incidence cycle with 3 vertices whose degree 2 are represented in Figs. 3.1 and 3.2.

Fig. 3.1

FIP P2˜ .

Fig. 3.2

Fuzzy Incidence cycle C3˜ .

Let V₁, E₁, FI₁ are the vertex set, edge set and Fuzzy Incidence pair set of P2˜ whose membership values are listed below.

Let V₂, E₂, FI₂ are the vertex set, edge set and Fuzzy Incidence pair set of C3˜ whose membership values are listed below.

Now taking the cartesian product of FIP P2˜ and Fuzzy Incidence cycle C3˜ such that P2˜×C3˜ with 6 vertices along with its membership values is represented in Fig. 3.3 satisfying the following conditions

Here, (σ₁ × σ₂) (t₁₁, t₂₁) ⩽ σ₁ (t₁₁) ∧ σ₂ (t₂₁) ⩽ 0.7 ∧ 0.4 ⩽ 0.4

Fig. 3.3

Cartesian product of P2˜×C3˜ .

Proof. Let G1˜(σ1,μ1,ψ1) and G2˜(σ2,μ2,ψ2) are two FIGs then to prove the cartesian product of G1˜×G2˜ is also a FIG.

Let σ₁, σ₂ be the Fuzzy Incidence subsets of the vertex sets V₁, V₂, μ₁, μ₂ be the Fuzzy Incidence subsets of the edge sets E₁, E₂, and ψ₁, ψ₂ be the Fuzzy Incidence subsets of the Fuzzy Incidence pair sets Ψ₁, Ψ₂.

By Definition 3.1, the cartesian product of FIGs,

Thus σ = σ₁ × σ₂ is the Fuzzy Incidence subset of the vertex set V = V₁ × V₂, μ = μ₁ × μ₂ is the Fuzzy Incidence subset of the edge set E = E₁ × E₂ and ψ₁ × ψ₂ is the Fuzzy Incidence subset of the Fuzzy Incidence pair set Ψ = Ψ₁ × Ψ₂. Therefore (G1˜×G2˜)(σ1×σ2,μ1×μ2,ψ1×ψ2) is a FIG.

Hence the cartesian product of any two FIGs is also a FIG.■

Theorem 3.1. The FICN for the cartesian product of FIPs Pm˜ and Pn˜ is

Proof. Let (Pm˜×Pn)˜(σ,μ,ψ) be a cartesian product of FIPs Pm˜(σ1,μ1,ψ1) and Pn˜(σ2,μ2,ψ2) . Let σ₁ ={ v₁, v₂, v₃, …, v_m } be a vertex set of degree 2 with m vertices and σ₂ ={ t₁, t₂, t₃, …, t_n } be a vertex set of degree 2 with n vertices. Let μ₁ ={ v₁v₂, v₂v₃, …, v_m-1v_m } be the set of edges incident with σ₁ and μ₂ ={ t₁t₂, t₂t₃, …, t_n-1t_n } be the set of edges incident with σ₂. Let ψ₁ ={ (v₁, v₁v₂) , (v₂, v₁v₂) , …, (v_m, v_m-1v_m) } be the set of Fuzzy Incidence pairs of σ₁ and μ₁ and ψ₂ ={ (t₁, t₁t₂) , (t₂, t₁t₂) , …, (t_n, t_n-1t_n) } be the set of Fuzzy Incidence pairs of σ₂ and μ₂.

By Definition 3.1 and Proposition 3.1, the cartesian product of any two FIGs must satisfies the following

Let the adjacent FIs of ψ [(v₁, t₁) , (v₁, t₁) (v₁t₁, v₁t₂)] are ψ [(v₁, t₂) , (v₁, t₁) (v₁t₁, v₁t₂)], ψ [(v₁, t₂) , (v₁, t₂) (v₁t₂, v₂t₂)], ψ [(v₁, t₁) , (v₁, t₁) (v₁t₁, v₂t₁)], ψ [(v₂, t₁) , (v₁, t₁) (v₁t₁, v₁t₂)], . . . . By Definition 2.7, color 1 for the FI ψ [(v₁, t₁) , (v₁, t₁) (v₁t₁, v₁t₂) and distinct colors for the adjacent incidences. It is impossible to color adjacent FIs in the same color. Color all of the FIs of the cartesian product of the FIG with minimum colors in the same way. Since the two FIPs Pm˜ and Pn˜ with m and n vertices have a vertex degree of 2. Any coloring for the cartesian product of two FIPs will result in m × n mesh, whose adjacent FIs to be colored with different colors. The cartesian product of two FIPs falls in two cases.

Here is the cartesian product graph with m × n rows and columns as a mesh. In this graph, the number of rows or columns is 3 and above such that exactly 6 colors are needed to color all the adjacent incidences of the mesh. Thus χψ(Pm˜×Pn˜)=6ifm⩾3andn⩾m . ■

Example 3.2. Let us consider two FIPs P3˜ and P4˜ with 3 and 4 vertices respectively represented in Figs. 3.4 and 3.5.

Fig. 3.4

FIP P3˜ .

Fig. 3.5

FIP P4˜ .

Applying cartesian product of two FIPs P3˜andP4˜ such that P3˜×P4˜ is represented in Fig. 3.6 satisfying the following conditions

Fig. 3.6

Cartesian product of FIPs P3˜×P4˜ .

The membership values of the vertices, edges for the cartesian product of P3˜×P4˜ is represented below

The membership functions of the FIs are represented as φ₁, φ₂, φ₃, φ₄, φ₅, φ₆ in Table 3.1.