Proper edge coloring of direct product of path and star fuzzy graphs

Bacha Khan; Tabasam Rashid; Ismat Beg

doi:10.55976/dma.42026150224-42

Home /

Archives /

Decision Making and Analysis, Volume 4 Issue 1, 2026 /

Original Research

Proper edge coloring of direct product of path and star fuzzy graphs

Bacha Khan ¹ , Tabasam Rashid ² , Ismat Beg ³ ^*

1. University of Management and Technology, Lahore, Pakistan
2. University of Management and Technology, Lahore, Pakistan
3. Lahore School of Economics, Lahore, Pakistan

Correspondence: ibeg@lahoreschool.edu.pk

DOI: https://doi.org/10.55976/dma.42026150224-42

Received

15 December 2025
Revised

15 February 2026
Accepted

05 March 2026
Published

15 May 2026

Fuzzy path graphs Fuzzy star graphs Direct product of fuzzy graphs Proper edge coloring Fuzzy chromatic number

Abstract

This research explored adjacent vertex distinguishing proper edge coloring (AVDPEC) in the context of the direct product of fuzzy graphs, with particular emphasis on combinations of fuzzy path and fuzzy star graph. In this study, the classical coloring theory of crisp graphs were applied to fuzzy graphs, as membership values introduce an additional layer of intricacy to them. The main contribution of this research is an algorithm for the direct product of fuzzy path and fuzzy star networks, which acquires appropriate edge coloring that distinguishes adjacent vertices utilizing fuzzy membership values. In applications where recognizing between entities or tasks is crucial, this algorithm ensures that each adjacent vertex pair in the fuzzy graph product is identified by the specific colors of their incident edges. By using fuzzy membership values, we provided a versatile structure for managing complicated systems with incomplete or probabilistic interactions between nodes. We also introduced two significant applications of this edge coloring technique: load balancing in data networks and task parallelism in parallel computing. All things considered, our work strengthens the concept of AVDPEC in uncertain graphs, which benefits graph theory both hypothetically and essentially.

<h5>1. Introduction</h5>
Graph theory is a branch of mathematics that examines the associations and configurations of networks. A mathematical framework is utilized by graph theory to display numerous relationships between objects. The collections of edges and vertices are the two sets that structure a graph. The objects in a graph are addressed by the vertices, while the associations or networks amongst those objects are represented by the edges. Graph theory has been widely used across different disciplines to resolve real-world problems. For example, traffic networks can be demonstrated utilizing graphs where crossing points are addressed as vertices and roads as edges. However, classical graph theory, regardless of its broad use, has specific impediments while managing inadequate or dubious information. For example, the traffic congestion at an intersection is caused by various uncertain factors, including the quantity of vehicles, the cycle length of traffic signals, poor road conditions, and so on.
To address the limitations of classical graph theory, particularly in dealing with vulnerabilities, the concept of fuzzy sets was introduced by Zadeh <a href="#reference_list_0">[1]</a> in 1965. Fuzzy set theory provides a quantitative framework for addressing vulnerability, vagueness, and uncertainty. When there are ambiguous boundaries amongst distinct states or classes, it provides a way to handle the situation. Instead of having a crisp binary value of 0 or 1, a fuzzy graph is an expansion of a classical graph in which each vertex or edge is linked with a degree of membership in the interval [0‚1]. Fuzzy graphs were first proposed by Kaufmann <a href="#reference_list_1">[2]</a>, who developed a fundamental definition based on Zadeh's concept of fuzzy relations. In this manner, Rosenfeldand Mutab <a href="#reference_list_2">[3, 4]</a> extended the definition of fuzzy graphs by introducing the idea of fuzzy vertices and fuzzy edges. Generally, a fuzzy graph can more effectively represent circumstances where the connections between objects are not rigorously binary but instead have fluctuating degrees of association. For instance, consider a social network where individuals are represented by vertices and the connections between them are represented by edges. In a classical graph, an edge either exists or does not, indicating the presence or absence of a relationship between two individuals. However, as a general rule, connections can have varying strengths, some individuals are close companions, while others are merely acquaintances. A fuzzy graph can capture these subtleties by relegating a membership degree to each edge, representing the strength of the relationship. For further information on fuzzy graph research, readers may consult <a href="#reference_list_4">[5-9]</a>.
In graph theory, graph coloring is a significant issue and it has significant hypothetical and viable importance. It involves assigning colors to certain elements of a graph, typically vertices or edges, subject to specific constraints. The purpose of graph coloring is to guarantee that neighboring or related components do not have a similar variety, thereby resolving conflicts in different real-world problems such as scheduling, frequency assignment, and resource allocation. In classical graph theory, the most essential kind of graph coloring is vertex coloring <a href="#reference_list_9">[10, 11]</a>, where colors are allocated to the vertices of a graph so that no two adjacent vertices share a similar color. This issue is known as proper vertex coloring. Similarly, proper edge coloring, local edge colouring and note on edge colouring <a href="#reference_list_11">[12-14]</a> are specific types of graph coloring in which colors are allocated to the edges of a graph to such an extent that no two edges incident on a similar vertex share a similar color. The minimum number of colors required to color a graph G is named the chromatic number of G, represented by χ (G). Zhang <a href="#reference_list_14">[15, 16]</a> presented the idea of adjacent strong edge coloring of graphs and adjacent strong edge colorings and total colorings of regular graph. Later on researchers <a href="#reference_list_16">[17-20]</a>, proposed the idea of AVDPEC guess in light of the conversation of the neighboring vertex differentiating proper edge chromatic numbers of trees, circles, complete bipartite graphs, and complete graphs. In which not only the edges must be properly colored, but for any pair of contiguous vertices u and v, the set of colors incident to u must be distinct from the set of colors incident to v. This type of coloring is particularly valuable in applications where adjacent vertices should be extraordinarily recognizable in view of the edges incident to them. The adjacent vertex differentiating proper edge chromatic number, denoted by χa (G), is the minimum possible number of colors expected to accomplish an AVDPEC of a graph G. Some basic operations of graphs and coloring discussed with some computations <a href="#reference_list_20">[21-24]</a>.
Considering that the coloring of fuzzy graph assumes an indispensable part in practical issues such as task and conflict coordination, an ever increasing number of researchers are dedicated to the investigation of fuzzy graph coloring issues. In classical graph theory, there are still a lot of coloring issues that have not yet tracked down comparing classifications in fuzzy graphs, such as the AVDPEC of the direct product of two fuzzy graphs. This gap will be filled through this study, which focuses on exploring the AVDPEC in the context of the direct product of fuzzy path and fuzzy star graphs. The edges of the direct product of fuzzy path and fuzzy star graphs are colored using a structured algorithm that guarantees proper edge coloring and satisfies the neighboring vertex differentiating constraint. In order to accomplish AVDPEC in fuzzy graphs, this research investigated a key approach. For the α-cut of G, the key technique relies on the advanced coloring AVDPEC function fα of the crisp graph Gα (V, Eα). A subset of a fuzzy graph known as the α-cut arises when the edge membership values are greater than or equal to a certain threshold, α. The edges of the fuzzy graph are colored according to the AVDPEC criteria by gradually coloring the crisp graph Gα. An extension of the idea of the AVDPEC function through a space defined by colors, forms the groundwork of the subsequent approach. The support graph of the fuzzy graph, which takes into account the entire range of membership values rather than just the α-cut, serves as the groundwork for this extended coloring function.
Fuzzy graph theory has made significant advancements to address various levels of uncertainty and relationship pattern dynamics within the graph. In addition to traditional fuzzy graph theory, there are various extensions to these graph models. Fuzzy hypergraphs address relationship patterns among multiple nodes simultaneously, and then fuzzy directed graphs address the direction of relationship patterns. Fuzzy super hypergraphs that address relationship patterns among multiple nodes simultaneously for various vertex sets. A deeper definition for these membership patterns is found and they are discussed in intuitionistic fuzzy graphs, which consider both membership and non-membership in these graph structures. They take this graph representation to another level by introducing neutrosophic directed graphs, which include the degree of indeterminacy. More advanced graph representations include plithogenic graphs, which consider multiple attributes for these graph structures. Another advanced graph representation model is then quadripartitioned neutrosophic graph, which addresses multi-dimensional uncertainties for these graph structures. These various graph structure models adjust characteristics such as graph coloring relative to their membership, degree of indeterminacy, or various graph attribute constraints.
Much work has carried out by many researchers; for example, Fujita’s contribution in hyper fuzzy sets and neutrosophic sets is remarkable <a href="#reference_list_24">[25, 26]</a>. An application of extended plithogenic sets in the form of a plithogenic sociogram was proposed by Sudhs <a href="#reference_list_26">[27]</a>, which has opened the door for many researchers in this area. Distance measures of picture fuzzy sets and interval valued picture fuzzy sets were proposed by Zhu <a href="#reference_list_27">[28]</a>. This study advances combinatorics in uncertain environments by employing graph and hypergraph structures, enriched with fuzzy, neutrosophic, soft set, rough set, and bipolar modeling approaches. For clarity in distinguishing between proposed concepts and conventional methods, we have listed the distinctions and improvements below. For instance, in conventional fuzzy graphs analogous to the proposed fuzzy graph concept, conditions concerning membership values are generally predetermined. The proposed concept, besides encompassing fuzzy graph structure, is capable of accommodating α-level structures. Furthermore, in the proposed concepts, vertex distinguishable proper edge coloring of conventional adjacency graphs is extended to fuzzy direct product graphs.
                                            Table 1. Concise comparison among assumptions, limitations, extensions, and contributions of study
<img src="https://file.luminescience.cn/6a056a4debbfb1778739789" alt="" width="650" height="253" />
Table 1 presents a concise comparison highlighting the assumptions, limitations, extensions, and contributions of this work relative to the closest existing concepts. To better understand the relationship between fuzzy graphs and crisp graphs, α-cuts are the most effective tools for analysing the coordination. The chromatic invariant in fuzzy graph theory is the focus of this study. The emphasis shifts to distinguishing how uncertainty in edge participation can be molded through fuzzy membership values, which induces an entire group of structurally distinct α-level graphs whose coloring behavior needs to be analyzed in aggregate. This approach enables the researchers to assess chromatic requirements across a range of confidence levels – a capability that no single crisp realization can offer.
In the preliminary segment, the ADVPEC of fuzzy graphs based on the above approach will be discussed in detail, providing the foundation for applying the strategy to the direct product of fuzzy path and fuzzy star graphs. As a result, this research offers an in-depth technique for resolving the AVDPEC issue in fuzzy graphs, focusing on the direct product of fuzzy path and fuzzy star graphs. We will inspect two key applications that affect the AVDPEC structure in this exploration. The first is task parallelism in parallel computing, where the efficient allocation and execution of tasks on multiple processors require careful management of task dependencies. The  second is load balancing in data networks, where distributing the load across network nodes while ensuring efficient communication and avoiding interference is a primary objective. The results presented in this study offer a foundation for further research in both graph theory and its applications in computing and networking.
In this proposed study, we have added different sections to help the reader better understand the sequence. Section 1 contains the introduction, and section 2 presents the literature review, basic and essential definitions, which are helpful to better understand the proposed work. In section 3, algorithm is added, in section 4 the algorithm's validity and useful results with explained figures are illustrated. Section 5 contains computational validity. Section 6 discusses real-life application and finally, section 7 describes the conclusion of the proposed study.
Motivation and novelty of the work
The theory of fuzzy graphs has been extensively used for modeling uncertain and incomplete information in graphs in the areas of communications, infrastructure planning, and decision-making processes. Various models and methods have been developed to study coloring properties and structural invariants of fuzzy graphs. Although the models of adjacent vertex distinguishing edge coloring in paths and cycles of fuzzy graphs has been studied earlier, less attention has been paid to the study on the behavior of this property in the construction of direct products of graphs. The aim of this research is to fill this research gap.
To read more details, please download the <a href="https://ojs.luminescience.cn/DMA/article/view/502/452">PDF</a> to see the full text.
<h5>7. Conclusion</h5>
In this research, a systematic presentation of the AVDPEC of fuzzy graph products is provided, with particular emphasis on fuzzy path and star graphs. This approach establishes a schematic method for determining the AVDPEC of fuzzy direct products, which can be readily generalized to a wide range of intricate fuzzy graph constructions. Our findings demonstrate that this algorithm efficiently calculates the minimal number of colors required to color the direct product so that every pair of neighboring vertices in it can be distinguished while taking into consideration their respective edge memberships. These can be seen to have analytical proofs, involving algorithms and examples that determine its correctness and computational efficiency. The relevance and significance of the study are evident in its applications in the context of giant graphs in which the connectivity may be uncertain, specifically in neural networks, social, and broadcast graphs. The incorporation of fuzziness in membership variety has efficiently enhanced the relevance and applicability of AVDPEC. In this scenario, the "greedy algorithm for the α-cut" in the context of the problem will ensure the appropriateness and vertex distinguishing property of the coloring technique, aiming to use the fewest number of colors, thus directly addressing issues of resource allocation, equality in data graphs, and task allocation in parallel computing networks. Though in the research paper, the methodology is explained with examples in connection with fuzzy direct products of paths and stars, still this proposed framework is quite easy to extend to address complicated graphs. The areas, which can be extended in this research include fuzzy directed graphs, bidirected graphs, hypergraphs, and super hyper graphs. It is important to mention that incorporating these areas will significantly contribute to opening new research directions for specifying uncertainty and multi-attribute relations in complicated graphs, as highlighted in previous literature ([references related to fuzzy directed graphs, hypergraphs, and super hyper graphs]). In summary, the present work has succeeded in moving the frontiers of knowledge regarding the computation of the Average Vertex Degree Product Eigenvalue Coloring Problem in fuzzy graph products. By its success, this research will pave the way not only for practical implementations in network management but also for ways in various researches in fuzzy graph theory.
<h5>Authors' contribution</h5>
Bacha Khan: Conceptualization, methodology and writing – original draft. Tabasam Rashid: Conceptualization, methodology, validation, supervision and writing – review & editing. Ismat Beg: Conceptualization, methodology, validation and editing.
<h5>Conflicts of interest</h5>
The authors declare that there is no conflict of interest.
<h5>Data availability statement</h5>
No data sets were generated or analyzed for the research described in this article.
<h5>Funding</h5>
No funding used from any source.

References

[1]Zadeh LA. Fuzzy sets. Information and control. 1965;8(3): 338-353. doi: 10.1016/S0019-9958(65)90241-X.

[2]Kaufmann A, Swanson DL. Introduction to the theory of fuzzy subsets. New York: Academic press. 1975;1: 42-180.

[3]Mutab HMA. Fuzzy Graphs. Journal of Advances in Mathematics. 2019;17: 232-247. doi: 10.24297/jam.v17i0.8443.

[4]Rosenfeld A. Fuzzy graphs. In: Zadeh LA, Fu KS, Shimura M. (eds.). Fuzzy sets and their applications to cognitive and decision processes. New York: Academic Press; 1975. p. 77-95. doi:10.1016/B978-0-12-775260-0.50008-6.

[5]Mordeson JN, Chang-Shyh P. Operations on fuzzy graphs. Information Sciences. 1994;79(3-4): 159-170. doi: 10.1016/0020-0255(94)90116-3.

[6]Molodtsov D. Soft set theory first results. Computers & Mathematics with Applications. 1999;37(4-5): 19-31. doi:10.1016/S0898-1221(99)00056-5.

[7]Raut S, Pal M. On chromatic number and perfectness of fuzzy graph. Information Sciences. 2022;597: 392-411. doi: 10.1016/j.ins.2022.03.050.

[8]Gong Z, Zhang J. Chromatic Number of fuzzy graphs: Operations, fuzzy graph coloring, and applications. Axioms. 2022;11(12): 697. doi:10.3390/axioms11120697.

[9]Sebastian A, Mathew S, Mordeson JN. A new fuzzy graph parameter for the comparison of human trafficking chains. Fuzzy Sets and Systems. 2022;450: 27-46. doi: 10.1016/j.fss.2022.04.016.

[10]Malaguti E, Monaci M, Toth P. An exact approach for the vertex coloring problem. Discrete Optimization. 2011;8(2): 174-190. doi: 10.1016/j.disopt.2010.07.005.

[11]Maheswari AU, Purnalakshimi AS, Samuvel BJ. Rainbow dominator coloring for special graphs. International Journal of Mechanical Engineering. 2022;7(5): 125-133.

[12]Deepa P, Srinivasan P, Sundarakannan M. Local edge coloring of graphs. AKCE International Journal of Graphs and Combinatorics. 2021;18(1): 29-32. doi: 10.1080/09728600.2021.1915722.

[13]Hadiputra FF, Maryati TK. A note on local edge antimagic chromatic number of graphs. Proyecciones (Antofagasta). 2024;43(2): 447-458. doi: 10.22199/issn.0717-6279-6014.

[14]Petruševski M, Škrekovski R. Proper edge-colorings with a rich neighbor requirement. Discrete Mathematics. 2024;347(3): 113803. doi: 10.1016/j.disc.2023.113803.

[15]Zhang Z, Liu L, Wang J. Adjacent strong edge coloring of graphs. Applied Mathematics Letters. 2002;15(5): 623-626. doi: 10.1016/S0893-9659(02)80015-5.

[16]Zhang ZF, Woodall DR, Yao B, Li JW, Chen XE, Bian L. Adjacent strong edge colorings and total colorings of regular graphs. Science in China Series A: Mathematics. 2009;52(5): 973-980. doi: 10.1007/s11425-008-0153-5.

[17]Chen X, Li Z. Adjacent-vertex-distinguishing proper edge colorings of planar bipartite graphs with Δ = 9, 10, or 11. Information Processing Letters. 2015;115(2): 263-268. doi: 10.1016/j.ipl.2014.09.025.

[18]Balister PN, Gyori E, Lehel J, Schelp RH. Adjacent vertex distinguishing edge colorings. Siam Journal on Discrete Mathematics. 2007;21(1): 237-250. doi: 10.1137/S0895480102414107.

[19]Zhang Z, Chen X, Li J, Yao B, Lu X, Wang J. On adjacent vertex distinguishing total coloring of graphs. Science in China Series A: Mathematics. 2005;48(3): 289-299.

[20]Behzad M. Graphs and their chromatic numbers [PhD thesis]. East Lansing, MI: Michigan State University; 1965. doi: 10.25335/j5he-k143.

[21]Fink JF, Straight HJ. A note on path perfect graphs. Discrete Mathematics. 1981;33(1): 95-98. doi: 10.1016/0012-365X(81)90262-4.

[22]Qiu K, Akl SG. On some properties of the star graph. VLSI Design. 1995;4(2): 389-396. doi: 10.1155/1995/61390.

[23]Nelson AM. Internal direct products and the universal property of direct product groups. Formalized Mathematics. 2023;31(1): 101-120. doi: 10.2478/forma-2023-0010.

[24]Gong Z, Zhang C. Adjacent Vertex Distinguishing Coloring of Fuzzy Graphs. Mathematics. 2023;11(10): 2233. doi: 10.3390/math11102233.

[25]Fujita T, Smarandache F. Examples of fuzzy sets, hyperfuzzy sets, and superhyperfuzzy sets in climate change and the proposal of several new concepts. Climate Change Reports. 2025;2: 1-18. doi: 10.61356/j.ccr.2025.2485.

[26]Fujita T, Smarandache F. Local-neutrosophic logic and local-neutrosophic sets: incorporating locality with applications. Multicriteria Algorithms with Applications. 2025;6: 66-86. doi: 10.61356/j.mawa.2025.6457.

[27]Sudha S , Martin N , Smarandache F. Applications of Extended Plithogenic Sets in Plithogenic Sociogram. International Journal of Neutrosophic Science. 2023;20(4): 08-35. doi:10.54216/IJNS.200401.

[28]Zhu S, Liu Z. Distance measures of picture fuzzy sets and interval-valued picture fuzzy sets with their applications. AIMS Math. 2023;8(12): 29817-29848. doi: 10.3934/math.20231525.

Download PDF

Download XML

How to Cite

Khan, B., Rashid, T., & Beg, I. (2026). Proper edge coloring of direct product of path and star fuzzy graphs. Decision Making and Analysis, 4(1), 24–42. https://doi.org/10.55976/dma.42026150224-42

Download Citation

Issue

Decision Making and Analysis, Volume 4 Issue 1, 2026

Section

Original Research

License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Copyright licenses detail the rights for publication, distribution, and use of research. Open Access articles published by Luminescience do not require transfer of copyright, as the copyright remains with the author. In opting for open access, the author(s) should agree to publish the article under the CC BY license (Creative Commons Attribution 4.0 International License). The CC BY license allows for maximum dissemination and re-use of open access materials and is preferred by many research funding bodies. Under this license, users are free to share (copy, distribute and transmit) and remix (adapt) the contribution, including for commercial purposes, providing they attribute the contribution in the manner specified by the author or licensor.

Home /

Archives /

Decision Making and Analysis, Volume 4 Issue 1, 2026 /

Original Research

Proper edge coloring of direct product of path and star fuzzy graphs

Abstract

How to Cite

Issue

Section

License

Follow Luminescience

Further Information

Home / Archives / Decision Making and Analysis, Volume 4 Issue 1, 2026 / Original Research

Proper edge coloring of direct product of path and star fuzzy graphs

Abstract

How to Cite

Issue

Section

License

Follow Luminescience

Further Information

Home /

Archives /

Decision Making and Analysis, Volume 4 Issue 1, 2026 /

Original Research