Coloring picture fuzzy graphs through their cuts and its computation

Abstract

In a fuzzy set (FS), there is a concept of alpha-cuts of the FS for alpha in [0,1]. Further, this concept was extended into (alpha,delta)-cuts in an intuitionistic fuzzy set (IFS) for delta in [0,1]. One of the expansions of FS and IFS is the picture fuzzy set (PFS). Hence, the concept of (alpha,delta)-cuts was developed into (alpha,delta,beta)-cuts in a PFS where beta is an element of [0,1]. Since a picture fuzzy graph (PFG) consists of picture fuzzy vertex or edge sets or both of them, we have an idea to construct the notion of the (alpha,delta,beta)-cuts in a PFG. The steps used in this paper are developing theories and algorithms. The objectives in this research are to construct the concept of (alpha,delta,beta)-cuts in picture fuzzy graphs (PFGs), to construct the (alpha,delta,beta)-cuts coloring of PFGs, and to design an algorithm for finding the cut chromatic numbers of PFGs. The first result is a definition of the (alpha,delta,beta)-cut in picture fuzzy graphs (PFGs) where (alpha,delta,beta) are elements of a level set of the PFGs. Further, some properties of the cuts are proved. The second result is a concept of PFG coloring and the chromatic number of PFG based on the cuts. The third result is an algorithm to find the cuts and the chromatic numbers of PFGs. Finally, an evaluation of the algorithm is done through Matlab programming. This research could be used to solve some problems related to theories and applications of PFGs.

Headnote

ABSTRACT

In a fuzzy set (FS), there is a concept of alpha-cuts of the FS for alpha in [0,1]. Further, this concept was extended into (alpha,delta)-cuts in an intuitionistic fuzzy set (IFS) for delta in [0,1]. One of the expansions of FS and IFS is the picture fuzzy set (PFS). Hence, the concept of (alpha,delta)-cuts was developed into (alpha,delta,beta)-cuts in a PFS where beta is an element of [0,1]. Since a picture fuzzy graph (PFG) consists of picture fuzzy vertex or edge sets or both of them, we have an idea to construct the notion of the (alpha,delta,beta)-cuts in a PFG. The steps used in this paper are developing theories and algorithms. The objectives in this research are to construct the concept of (alpha,delta,beta)-cuts in picture fuzzy graphs (PFGs), to construct the (alpha,delta,beta)-cuts coloring of PFGs, and to design an algorithm for finding the cut chromatic numbers of PFGs. The first result is a definition of the (alpha,delta,beta)-cut in picture fuzzy graphs (PFGs) where (alpha,delta,beta) are elements of a level set of the PFGs. Further, some properties of the cuts are proved. The second result is a concept of PFG coloring and the chromatic number of PFG based on the cuts. The third result is an algorithm to find the cuts and the chromatic numbers of PFGs. Finally, an evaluation of the algorithm is done through Matlab programming. This research could be used to solve some problems related to theories and applications of PFGs.

Keywords

Picture fuzzy graph Coloring graph Cuts Chromatic number Intuitionistic Fuzzy set

(ProQuest: ... denotes formulae omitted.)

1. Introduction

Zadeh first introduced the fuzzy set (FS) theory in 1965 that could be used to handle indeterminate phenomena in real-life problems [1]. Every member in the FS is assigned to a single value of membership degree. However, in real problems, sometimes people want to know a degree of non-membership of an element. To deal with this problem, Atanassov initiated an intuitionistic fuzzy set (IFS) where there are membership and non-membership degrees of each element [2]. Recently, Cuong constructed a picture fuzzy set (PFS), an extension of FS and IFS theories, by adding a neutral membership degree for each element [3]. In other words, there are three types of degrees assigned to each element in the PFS (i.e., positive, negative, and neutral membership degrees). Some aspects of the PFS have also been investigated [4][5].

Based on FS's fuzzy relation, Rosenfeld proposed a fuzzy graph to deal with indeterminacy in a network [1]. After that, an intuitionistic fuzzy graph (IFG) has also been constructed through the concept of intuitionistic fuzzy relation [6], [7]. Nowadays, a concept of picture fuzzy graph (PFG) has been initiated by means of picture fuzzy relation [8] [9]. Further, Zuo et al. [10] gave some operations on PFG, i.e., union, join, and cartesian product. Meanwhile, Xiao et al. [11] studied regular PFGs and provided some properties of them. Furthermore, Ismayil et al. [12] investigated an edge domination problem in PFGs, Jayalakshmi and Vidhya [13] initiated a direct sum on PFGs, and Talebi et al. [14] determined energy in PFGs. In addition, some scholars verified applications of PFGs, such as in Koczy et al. [15], Mohanta et al. [16], Das and Ghorai [17] [18], Das et al. [19] [20], Sitara et al. [21], and Mani et al. [22].

The concept of а-cuts of an FS for ae[0,1] was first proposed by Zadeh [1]. Further, the a-cuts were extended into a,8-cuts in an IFS [2]. Furthermore, Cuong and Kreinovich expanded the concept into the a,5,ß-cuts in a PFS [3]. This background motivated us to develop the cuts in picture fuzzy graphs (PFGs). The concepts of fuzzy graph coloring and IFG coloring have been proposed by researchers [23] - [29]. However, no researchers discussed the concept of coloring in the PFGs until now. Therefore, the objectives of this research are as follows: to develop the concept of a,5,ß-cuts in picture fuzzy graphs (PFGs) because the PFGs consist of picture fuzzy vertex or edge sets or both of them; to investigate some properties of the a,5,ß-cuts in the PFGs; to construct a concept of PFG coloring and the chromatic number of PFG based on the a,5,ß-cuts; and to design an algorithm for determining the cuts and the chromatic number of the PFGs. The last objective is to evaluate the algorithm through Matlab programming. These are novelties of this research.

We organize this paper in the following: introduction and some basic concepts are summarized in section 1. Further, the methods used in this research are given in section 2. Moreover, the construction of the a,5,ß-cuts of PFGs and the cuts' properties, a coloring concept of PFGs based on the cuts, and an algorithm are described in section 3. The conclusion and upcoming research are given at the end section.

We discuss some basic concepts in PFGs in this section. Given a universe of discourse X. A fuzzy set A on X is a set {...}, where μÃ: X → [0,1] is mentioned as a membership function of the fuzzy set A. [1]

Definition 1. An intuitionistic fuzzy set (IFS) Л on X is a set of the form {...}, where μÃ(x) ∈ [0,1] is called a degree of membership of element x in A and vÃ(x) ∈ [0,1] is a degree of non-membership of element x in à which fulfill the condition ... . [2]

Definition 2. A picture fuzzy set (PFS) Л on X is a set of the form {...}, where μÃ(x) ∈ [0,1], ηÃ(x) ∈ [0,1], and vÃ(x) E [0,1], respectively represent a positive membership degree (PM), a neutral membership degree (NeuM), and a negative membership degree (NM) of element x in the PFS à which satisfy ... .

The value ... is named as a degree of refusal membership of x in Al. It is obvious that a PFS will be reduced into an IFS if ηÃ(x) = 0 for each x∈X. [3]

Definition 3. A picture fuzzy relation is defined as a PFS R on X X Y as follows

...

where ... [0,1], ... [0,1], and ... [0,1] meet the condition ... for each (a, b) ... . [3]

Given a universal set X. A subset, a union, and intersection between two picture fuzzy sets ... and ... are given below.

* The PFS A is a subset of B , denoted by A ę B, if [3]

...

* A union of PFSs A and B , symbolized by A U В, is a set [3]

...

2. Method

This research is theoretical research that includes the development of theories and the construction of an algorithm. The steps used in this research are as follows:

1) Developing a concept of a,8,ß-cut in the PFGs based on a,5,ß-cut of the PFS.

2) Investigating some properties of the a,5,ß-cuts of PFGs.

3) Defining coloring the PFGs through crisp coloring on the a,5,ß-cuts.

4) Defining the chromatic number, i.e., the minimum number to color vertices of PFGs, through the cut chromatic numbers.

5) Constructing an algorithm to determine the a,5,ß-cuts and the chromatic number of PFGs based on the previous steps' concepts.

6) Evaluating the algorithm through Matlab programming.

3. Results and Discussion

The main results in this paper are discussed in this section. Firstly, we develop the notion of level set and a,5,ß-cuts in picture fuzzy graphs (PFGs) as in Definition 3.2.1 and Definition 3.2.2.

3.1.a,5,ß-Cuts of picture fuzzy graphs (PFGs)

The concept of level set in Definition 3.1.1 is constructed based on the PFS level set concept as given in [5].

Definition 3.1.1. Given a graph ... and a PFG with picture fuzzy vertex and edge sets G (V, E) on G· where ... and ... . A level set of V is a set

...

Whereas, a level set of E is a set

... where h1, h2, h3 and G, t2, t3 are heights of PM, NeuM, and NM of Ѷ and E, respectively. A level set of the PFG is a set ... .

Further, the cut of PFGs in Definition 3.1.2 is developed based on the cut of PFS as introduced in [3]. Definition 3.1.2. Let G· = (V, E) be a graph. Let G (Ѷ, E) be a PFG on G·. Given ... where L is level set of the PFG and ... . An α, δ, ß-cut of G is a crisp graph ... for which

...

An interpretation of the chromatic number of the PFG is as follows:

* When the values α and δ are low and the value ß is high, there are a lot of adjacent vertices (more incompatible vertices). Hence, more colors are used for vertex coloring of G.

* Conversely, when the values α and δ are high, and the value ß is low, there are not so many adjacent vertices (less incompatible vertices). Hence, fewer colors are used for vertex coloring of G.

An illustration of an application of coloring of a PFG is given in the example as follows.

Example 3.3.1. Given a PFG G(V,E) where the vertex set V is a crisp set and edge set E is a PFS. The vertices in V represent traffic flows in an intersection. An edge between two vertices indicates that the two traffic flows are not compatible when they move in the same phase. The interpretations of degrees p(uv'), q(uv'), v(uv) are as follows:

* The degree p(uv') is the degree of incompatibility between the traffic flows u and v (traffic flows и and v are in conflict). The degree p(uv') can be obtained by fuzzifying the data of traffic flows that are in primary conflict (crossing).

* The degree v(uv) is the degree of compatibility between the traffic flows u and v (traffic flows и and v are not in conflict). The degree v(uv) can be obtained by fuzzifying the data of traffic flows that are not in conflict.

* The degree r¡ (uv) is the degree of indeterminacy whether the traffic flows u and v are compatible or not. The degree q(uv) can be obtained by fuzzifying the data of traffic flows that are not in primary conflict (merging).

Whereas, an interpretation of the chromatic number ... of the PFG is as follows: the number ... indicates the number of phase required to arrange traffic flows in an intersection. The meaning of degrees p, q, and r are as follows:

* The degree p (x) is the security level when we apply the number of phase x in an intersection.

* The degree r(x) is the level of insecurity when we apply the number of phase x in an intersection.

* The degree q(x) is the indeterminacy level whether the condition is secure or not when we apply the number of phase x in an intersection.

The lower values a and S and the higher value ß in the network indicate that we need to arrange traffic flows at a maximum security level since there are much incompatible traffic flows in the intersection, and vice versa.

Further, some properties of the cut chromatic numbers of the PFGs are verified.

Theorem 3.3.1. Let G(V, E) be a PFG on G· = (V, E). Let ..., where L is the level set of the PFG. If ..., then ... .

Proof. Let ... where ... . Based on Theorem 4.2.1, ... . According to a property of crisp chromatic number, we get ... . *

Theorem 3.3.2. Given a picture fuzzy graph G(V, E) on G· = (V, E) with ... . If a ... where ..., then ... .

Proof. According to Theorem 4.2.2, we get G α,δ,ß is a complete crisp graph with n vertices. Thus, its chromatic number is ... . *

Example 3.3.2. Given a PFG in Fig. 6 (left). Some α, δ, ß-cuts of the PFG and their chromatic numbers Acknowledgment

The authors thank the reviewers for their comments in the paper. The authors also thank the editorial team of IJAIN, who have proofread our paper.

Declarations

Author contribution. The first author contributed to the construction of definitions, theorems, and the algorithm in the results and discussion section. Meanwhile, the second author contributed to the evaluation of the algorithm. All authors read and approved the final paper.

Funding statement. None of the authors have received any funding or grants from any institution or funding body for the research.

Conflict of interest. The authors declare no conflict of interest.

Additional information. No additional information is available for this paper.

Sidebar

ARTICLE INFO

Article history

Selected paper from The 2020 3rd International Symposium on Advanced Intelligent Informatics (SAIN'20), Nanjing-China (Virtually), 25-26 November 2020, http://sain.ijain.org/2020/. Peer-reviewed by SAIN'20 Scientific Committee and Editorial Team of IJAIN journal.

Received October 31, 2020 Revised November 26, 2020 Accepted March 29, 2021 Available online March 31, 2021

References

References

[1] S. Mathew, J. N. Mordeson, and D. S. Malik, "Fuzzy Graph Theory," in Studies in Fuzziness and Soft Computing, Second., Switzerland: Springer Nature, 2018, pp. 13-76, doi: 10.1007/978-3-319-71407-3.

[2] K. T. Atanassov, "On intuitionistic fuzzy graphs and intuitionistic fuzzy relations," in Proceedings of the VI IFSA World Congress, 1995, pp. 551-554. Available at: Google Scholar.

[3] B. C. Cuong and V. Kreinovich, "Picture fuzzy sets - A new concept for computational intelligence problems," in 2013 3rd World Congress on Information and Communication Technologies, WICT, 2013, pp. 1-6, doi: 10.1109/WICT.2013.7113099

[4] B. C. Cuong, "Picture fuzzy sets," J. Comput. Sci. Cybern., vol. 30, no. 4, pp. 409-420, 2015, doi: 10.15625/1813-9663/30/4/5032.

[5] P. Dutta and S. Ganju, "Some aspects of picture fuzzy set," Trans. A. Razmadze Math. Inst., vol. 172, no. 2, pp. 164-175, 2018, doi: 10.1016/j.trmi.2017.10.006.

[6] B. Davvaz, N. Jan, T. Mahmood, and K. Ullah, "Intuitionistic Fuzzy Graphs of n Type with Applications," J. Intell. Fuzzy Syst., vol. 36, no. 4, pp. 3923-3932, 2019, doi: 10.3233/JIFS-181123

[7] M. Pal, S. Samanta, and G. Ghorai, "Intuitionistic Fuzzy Graphs," 2020, 1st ed., pp. 225-274, doi: https://doi.org/10.1007/978-981-15-8803-7_9, doi: 10.1007/978-981-15-8803-7_9.

[8] T. Al-hawary, T. Mahmood, N. Jan, and K. Ullah, "On Intuitionistic Fuzzy Graphs and Some Operations on Picture Fuzzy Graphs On Intuitionistic Fuzzy Graphs and Some Operations on," Ital. J. Pure Appl. Math. ·, vol. In Press, pp. 1-15, 2018, available at: Google Scholar.

[9] P. Dutta and K. Saikia, "Some aspects of Equivalence Picture Fuzzy Relation Palash," Adv. Model. Anal. A, vol. 172, no. 2, pp. 164-175, 2018, doi: 10.1016/j.trmi.2017.10.006.

[10] C. Zuo, A. Pal, and A. Dey, "New concepts of picture fuzzy graphs with application," Mathematics, vol. 7, no. 5, pp. 1-18, 2019, doi: 10.3390/math7050470.

[11] W. Xiao, A. Dey, and L. H. Son, "A study on regular picture fuzzy graph with applications in communication networks," J. Intell. Fuzzy Syst., vol. 39, no. 3, pp. 3633-3645, 2020, doi: 10.3233/JIFS-191913.

[12] M. Ismayil A, R. U. Rehman A, and R. Tejaskumar, "Edge Domination in Picture Fuzzy Graphs," Int. J. Comput. Eng. Res., vol. 09, no. 08, pp. 39-45, 2019. Available at: Google Scholar.

[13] S. Jayalakshmi and D. Vidhya, "On Direct Sum of Two Picture Fuzzy Graph," in AIP Conf. Proc., 2020, vol. 2277, no. 090004, pp. 1-7, doi: 10.1063/5.0025300.

[14] A. Talebi, H. Rashmanlou, and S. H. Sadati, "Several Notions of Energy in Picture Fuzzy Graphs," in 4th International Conference on Combinatorics, Criptography, Computer Science and Computing (I4C), 2019, pp. 200-228, available at: Google Scholar.

[15] L. T. Koczy, N. Jan, T. Mahmood, and K. Ullah, "Analysis of social networks and Wi-Fi networks by using the concept of picture fuzzy graphs," Soft Comput., vol. 24, no. 21, pp. 16551-16563, 2020, doi: 10.1007/s00500-020-04959-9.

[16] K. Mohanta, A. Dey, and A. Pal, "A study on picture dombi fuzzy graph," Decis. Manag. andEngineering, vol. 3, no. 2, pp. 119-130, 2020, doi: 10.31181/dmame2003119m.

[17] S. Das and G. Ghorai, "Analysis of the effect of medicines over bacteria based on competition graphs with picture fuzzy environment," Comput. Appl. Math., vol. 39, no. 3, pp. 1-21, 2020, doi: 10.1007/s40314-020-01196-6.

[18] S. Das and G. Ghorai, "Analysis of Road Map Design Based on Multigraph with Picture Fuzzy Information," Int. J. Appl. Comput. Math., vol. 6, no. 3, pp. 1-17, 2020, doi: 10.1007/s40819-020-00816-3.

[19] S. Das, G. Ghorai, and M. Pal, Certain Competition Graphs Based on Picture Fuzzy Environment with Applications, 2020, doi: 10.1007/s10462-020-09923-5, doi: 10.1007/s10462-020-09923-5.

[20] S. Das, G. Ghorai, and M. Pal, "Genus of Graphs Under Picture Fuzzy Environment with Applications," J. Ambient. Intell. Humaniz. Comput., 2021, doi: 10.1007/s12652-020-02887-y.

[21] M. Sitara, M. Akram, and M. Riaz, "Decision-Making Analysis Based on q-Rung Picture Fuzzy Graph Structures," J Appl Math Comput., 2021, doi: 10.1007/s12190-020-01471-z.

[22] P. Mani, B. Vasudevan, and M. Sivaraman, "Shortest path algorithm of a network via picture fuzzy digraphs and its application," Mater. Today Proc., 2021, doi: 10.1016/j.matpr.2020.12.006.

[23] M. Pal, S. Samanta, and G. Ghorai, "Coloring of Fuzzy Graph," 2020, 1st ed., pp. 175-193, doi: 10.1007/978-981-15-8803-7_7.

[24] I. Rosyida, Widodo, C. R. Indrati, D. Indriati, and Nurhaida, "Fuzzy Chromatic Number of Union of Fuzzy Graphs: An Algorithm, Properties and its Application," Fuzzy Sets Syst., vol. 384, pp. 115-131, 2020, doi: 10.1016/j.fss.2019.04.028.

[25] I. Rosyida, J. Peng, L. Chen, W. Widodo, C. R. Indrati, and K. A. Sugeng, "An Uncertain Chromatic Number of an Uncertain Graph Based on a-Cut Coloring," Fuzzy Optim Decis Mak., vol. 17, pp. 103-123, 2018, doi: 10.1007/s10700-016-9260-x.

[26] I. Rosyida, Widodo, C. R. Indrati, and D. Indriati, "On construction of fuzzy chromatic number of cartesian product of path and other fuzzy graphs," J. Intell. Fuzzy Syst., vol. 39, no. 1, pp. 1073-1080, 2020, doi: 10.3233/JIFS-191982.

[27] I. Rosyida, Widodo, C. R. Indrati, and K. A. Sugeng, "A New Approach for Determining Fuzzy Chromatic Number of Fuzzy Graph", J. Intell. Fuzzy Syst., vol. 28, no. 5, pp. 2331-2341, 2015, doi: 10.3233/IFS-141521.

[28] S. Ismail Mohideen and M. . Rifayathali, "Coloring of intuitionistic fuzzy graph using (alpha,beta)-cuts.," Int. Res. J. Math. Eng. IT, vol. 2, no. 12, pp. 14-26, 2015. Available at: Google Scholar.

[29] A. Prasanna, M. . Rifayathali, and S. Ismail Mohideen, "Strong intuitionistic fuzzy graphs," Int. J. Latest Eng. Res. Appl., vol. 02, no. 08, pp. 163-169, 2017, doi: 10.1007/s41478-018-0102-9.

[30] M. Ismayil, "Domination in Picture Fuzzy Graphs," in 5th International Conference on Mathematical Methods and Computation (ICOMAC - 2019), 2019, no. February, 20-21, pp. 205-210. Available at: Google Scholar.