Abstract
This study has come up with a new application of permuted cordial labeling initiated by two graphs based on their corona product, furthering the cause of a better comprehension of and research into specific types of graphs. The Permuted cordial labeling construction for the corona product of graphs consisting of paths, cycles, second power of a path and second power of cycle graphs may facilitate the consideration of the properties and structures of the graphs. It helps us to study its topological properties, connectivity images, symmetries and other properties.
1. Introduction
Graph theory is widely known to have applications in many other academic fields, including communication, physics, chemistry, biology, computer science, psychology, sociology, and economics [1, 2]. One area of graph theory that has received a lot of recent development is graph labelling. Labeled graphs are useful models for many fields, including as coding theory, circuit design, radar, X-ray crystallography, and database management [3].
A particular kind of graph labeling involves assigning values from an established set to its vertices, assigning an automatically induced label to its edges, and ensuring that the labeling satisfies certain conditions. On this subject, the paper by Gallian [4] is an excellent resource. Two of the most important categories are labeling that is graceful and harmonic. In 1966 and 1972, respectively, Rosa [5] and Golomb [6] separately developed graceful labeling, and in 1980, Graham and Sloane [7] concluded the first investigation on harmonic labeling.
A third important type of labeling that Cahit [8] developed in 1990 and which combines components of the other two is cordial labeling. Cordial labelings use labels 0 and 1, together with the induced label , which naturally equals , in contrast to graceful and harmonious labelings, which use labels and (modulo the number of edges), respectively. Since mathematics modulo 2 is an essential part of computer science, cordial labeling has a lot in common with that field. In [9] A. Abd El-hay and et.al, prove the corona product of paths and third power of lemniscate graph are signed product-cordial for all , and . In [10] ELrokh and et.al, proved that each path, cycle and Fan admits permuted cordial labeling. The Wheel graph , admits permuted cordial labeling except and even. Moreover, they proved that the union of , , admits a permuted cordial labeling for all . The union of , , admits a permuted cordial labeling for all , . The union of , , admits a permuted cordial labeling for all , . For more details about other labeling that are related to cordial labeling such as permuted logically, total cordial, signed product cordial, etc. the reader is referred to [10-17].
The rest of this paper is structured as follows: permuted cordial labeling for the corona product of paths, cycles, second power of paths, and second power of cycles are presented in Section 3. Section 4 proposes an algorithm for determining the permuted cordial labeling of a given graph. Section 5 investigate the discussion on Permuted Cordial Labeling and Its Engineering Applications. Finally, in Section 6, conclusions are drawn.
2. Materials and methods
We can use these code of labeling as follows.
Table 1Labeling methods
repeated time | repeated time | ||
repeated time | repeated time | ||
repeated time | repeated time | ||
repeated time | repeated time | ||
repeated time | repeated time | ||
repeated time | repeated time |
Sometimes, we modify , , and by adding symbols at one end or the other or both; for example, means the labeling (-times). Similarly, means the labeling (-time). , , and represent the number of vertices labeled , , and , respectively. Similarly, we denoted , , and to be the number of edges labeled , , and , respectively, for the graph .
A vertex labeling of graph of with induced edge labeling defined by:
is called permuted cordial labeling if and , and where (respectively, ) is the number of vertices (respectively, edges) labeled with . A graph is permuted cordial if it admits a permuted labeling. For a given labeling of the corona , we denote and () to represent the numbers of vertices and edges labeled by , respectively. We denote and to be the numbers of vertices and edges labeled by , respectively, for the graph . Also, we let , and , be those for , which are connected to the vertices labeled of . It is easy to verify that:
Finally, for particular labeling A and B that are used for and , respectively, we let denote the labeling for the corona of and . Section one contains a brief literary analysis of the topic of this work. Section Two deals with the Materials and Methods employed throughout. Whereas section three is devoted to studying the permuted cordial labeling for the corona product of paths, cycles, second power of paths, and second power of cycles. Section four proposes an algorithm for determining the permuted cordiality of a given graph. Section five investigated the discussion on Permuted Cordial Labeling and Its Engineering Applications. The last section is the conclusion which summarizes the important points of our finding in this paper.
3. Results
In this section we shall prove that the permuted cordial labeling for the corona product of paths, cycles, second power of paths, and second power of cycles.
Theorem 1. is permuted cordial for all and .
Proof. Let ( and ), and ( and ), then, we may use the labeling or for as given in Table . For a given value of with , , we may use one of the labeling in the set for , where , , , , and are the labeling of which are connected to the vertices labeled in , while , , , , and are the labeling of which are connected to the vertices labeled 𝑓 in as given in Table 3. Using Table 4 and the Eq. (1) and Eq. (2), we can compute the values shown in the last two columns of Table 4. Since all of these values are 1 or 0, the theorem follows.
Table 2Labeling of Pn
Table 3Labeling of Pm
Table 4Labeling of Pn⊙Pm
, , | , | ||||
0, 0, 0 | 0, 0, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
0, 0, 0 | 0, 0, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
0, 0, 0 | 0, 0, 0 | ||||
1, 1, 0 | 0, 0, 0 | ||||
1, 1, 0 | 1, 1, 0 |
Theorem 2. is permuted cordial for all and except at with .
Proof. Let ( and ), and ( and ), then, we may use the labeling or for as given in Table 5. For a given value of with , , we may use one of the labeling in the set for , where , , , , and are the labeling of which are connected to the vertices labeled in , while , , , , and are the labeling of which are connected to the vertices labeled 𝑓 in as given in Table 6. Using Table 7 and Eq. (1) and Eq. (2), we can compute the values shown in the last two columns of Table 7. Since all of these values are 1 or 0, the theorem follows.
Table 5Labeling of Cn
Table 6Labeling of Cm
Table 7Labeling of Cn⊙Cm
, | , | ||||
0, 0, 0 | 0, 0, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
0, 0, 0 | 0, 0, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
0, 0, 0 | 0, 0, 0 | ||||
1, 1, 0 | 1, 1, 0 |
Theorem 3. is permuted cordial for all and .
Proof. Let ( and ), and ( and ), then, we may use the labeling or for as given in Table 8. For a given value of with , , we may use one of the labeling in the set for , where , , , , and are the labeling of which are connected to the vertices labeled in , while , , , , and are the labeling of which are connected to the vertices labeled 𝑓 in as given in Table 9. Using Table 10 and Eq. (1) and Eq. (2), we can compute the values shown in the last two columns of Table 10. Since all of these values are 1 or 0, the theorem follows.
Table 8Labeling of Pn
Table 9Labeling of Cm
Table 10Labeling of Pn⊙Cm
, | , | ||||
0, 0, 0 | 0, 0, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
0, 0, 0 | 0, 0, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
0, 0, 0 | 0, 0, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
1, 1, 0 | 1, 1, 0 |
Theorem 4. is permuted cordial for all and .
Proof. Let ( and ), and ( and ), then, we may use the labeling or for as given in Table 11. For a given value of with , , we may use one of the labeling in the set for , where , , , , and are the labeling of which are connected to the vertices labeled in , while , , , , and are the labeling of which are connected to the vertices labeled 𝑓 in as given in Table 12. Using Table 13 and Eq. (1) and Eq.(2), we can compute the values shown in the last two columns of Table 13. Since all of these values are 1 or 0, the theorem follows.
Table 11Labeling of Cn
Table 12Labeling of Pm
Table 13Labeling of Cn⊙Pm
, | , | ||||
0, 0, 0 | 0, 0, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
0, 0, 0 | 0, 0, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
0, 0, 0 | 0, 0, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
1, 1, 0 | 1, 1, 0 |
Theorem 5. is permuted cordial for all and .
Proof. Let ( and ), and ( and ), then, we may use the labeling or for as given in Table 14. For a given value of with , , we may use one of the labeling in the set for , where , , , , and are the labeling of which are connected to the vertices labeled in , while , , , , and are the labeling of which are connected to the vertices labeled 𝑓 in as given in Table 15. Using Table 16 and Eq. (1) and Eq. (2), we can compute the values shown in the last two columns of Table 16. Since all of these values are 1 or 0, the theorem follows.
Table 14Labeling of Pn
Table 15Labeling of P2m
Table 16Labeling of Pn⊙P2m
, | , | ||||
0, 0, 0 | 0, 0, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
0, 0, 0 | 0, 0, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
0, 0, 0 | 0, 0, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
1, 1, 0 | 1, 1, 0 |
Theorem 6. is permuted cordial for all and .
Proof. Let ( and ), and ( and ), then, we may use the labeling or for as given in Table 17. For a given value of with , , we may use one of the labeling in the set for , where , , , , and are the labeling of which are connected to the vertices labeled in , while , , , , and are the labeling of which are connected to the vertices labeled 𝑓 in as given in Table 18. Using Table 19 and Eq. (1) and Eq. (2), we can compute the values shown in the last two columns of Table 19. Since all of these values are 1 or 0, the theorem follows.
Table 17Labeling of Pn
Table 18Labeling of C2m
Table 19Labeling of Pn⊙C2m
, | , | ||||
0, 0, 0 | 0, 0, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
0, 0, 0 | 0, 0, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
0, 0, 0 | 0, 0, 0 | ||||
1, 1, 0 | 1, 1, 0 | ||||
1, 1, 0 | 1, 1, 0 |
4. Algorithm
In this section, we propose an algorithm for calculating the permuted cordial labeling for any graph 𝐺. This algorithm provides a framework for attempting to find a permuted cordial labeling for a given graph. It’s important to note that not all graphs will admit a permuted cordial labeling, and the specific method of assigning labels to vertices in step 3 can vary based on the graph’s structure and properties. we assume that labeling each vertex and edge takes constant time, then the time complexity of Algorithm 1 is 𝑂(𝑛), since each vertex and edge is visited once.
Table 20Algorithm for Permuted cordial labeling of a graph
Algorithm1: Permuted Cordial Labeling of a Graph Input: graph Output: Permuted cordial labeling of if it exists |
Begin Step 1. Initialize three counters, , and , to 0. Step 2. Initialize three counters, , and , to 0. Step 3. For each vertex in : a. Assign a label to the vertex . b. If , increment ; else If , increment ; else increment . Step 4. For each edge in : a. Assign a label o to the edge . b. If , increment ; If , increment ; else increment . Step 5. Check the Permuted cordial condition: a. If and , and , : i. The labeling is cordial. ii. Output the labeling of vertices and edges. b. Else: i. The graph G does not admit a Permuted cordial labeling. ii. Output that no Permuted cordial labeling exists. End Algorithm |
5. Discussion
In graph theory, permuted cordial labeling is an intriguing idea with possible applications in a number of industrial domains. A graph's vertices are given labels using this labeling technique so that the total of the labels of nearby vertices satisfies predetermined requirements. In engineering applications, this idea can be useful in the following ways:
5.1. Network design and optimization
In telecommunications and computer networks, it is important for the efficient routing of data. Permuted cordial labeling can be a means of optimization for network topologies that can minimize the number of connections among them while still having robust communication paths. Applying this labeling, engineers are able to design networks with load balancing and low latency which in turn results in a better performance.
5.2. Resource allocation
In systems, wherein resources, such as bandwidth or power, must be allocated, the permuted cordial labeling becomes a just and effective model of distribution. E.g. In a wireless sensor network, this labeling will be a great deal in the arrangement of the sensor nodes in the way of having maximum coverage and minimum energy consumption.
6. Conclusions
We proved that each , , admits permuted cordial labeling. Each , , admits permuted cordial labeling for all , . Each , , admits a permuted cordial labeling. , , admits permuted cordial labeling.
Moreover, we proved that the corona of , , admits a permuted cordial labeling. Also, we proved the corona of , , admits a permuted cordial labeling. We proposed an algorithm for determining the Permuted cordial of a given graph. In the future, we will apply permuted cordial labeling to other types of graphs.
References
-
A. Krishnaa, “Some applications of labelled graphs,” International Journal of Mathematics Trends and Technology, Vol. 37, No. 3, pp. 209–213, Sep. 2016, https://doi.org/10.14445/22315373/ijmtt-v37p528
-
D. Narsingh, Graph Theoty with Application to Engineering and Computer Science. New Delhi, India: PrenticeHall of India Pvt., 2003.
-
N. Hartsfield and G. Ringel, Pearls in Graph Theory: a Comprehensive Introduction. Boston, USA: Academic Prress Inc., 1990.
-
J. A. Gallian, “A dynamic survey of graph labeling,” The Electronic Journal of Combinatorics, Vol. 1000, Dec. 2022, https://doi.org/10.37236/11668
-
A. Rosa, “On certain valuations of the vertices of a graph,” in Theory of Graphs, 1967.
-
S. W. Golomb, “How to number a graph in graph theory and computing,” in Graph Theory and Computing, pp. 23–37, Jan. 1972, https://doi.org/10.1016/b978-1-4832-3187-7.50008-8
-
R. L. Graham and N. J. A. Sloane, “On additive bases and harmonious graphs,” SIAM Journal on Algebraic Discrete Methods, Vol. 1, No. 4, pp. 382–404, Dec. 1980, https://doi.org/10.1137/0601045
-
I. Cahit, “On cordial and 3-equitable labeling of graphs,” Utilitas Mathematica, Vol. 37, pp. 189–198, 1990.
-
A. Abd El-Hay, Y. Elmshtaye, and A. Elrokh, “Solving singed product cordial labeling of corona products of paths and the third power of lemniscate graphs,” Turkish Journal of Computer and Mathematics Education (TURCOMAT), Vol. 14, No. 2, pp. 806–823, 2023, https://doi.org/10.17762/turcomat.v14i2.13737
-
A. Elrokh, M. M. A. Al-Shamiri, M. M. A. Almazah, and A. A. El-Hay, “A novel problem for solving permuted cordial labeling of graphs,” Symmetry, Vol. 15, No. 4, p. 825, Mar. 2023, https://doi.org/10.3390/sym15040825
-
A. Elrokh, Y. Elmshtaye, and A. Abd El-Hay, “The cordiality of cone and lemniscate graphs,” Applied Mathematics and Information Sciences, Vol. 16, No. 6, pp. 1027–1034, Nov. 2022, https://doi.org/10.18576/amis/160620
-
S. Nada, A. Elrokh, and A. Abd El-Hay, “On signed product cordial of lemniscate graph and its second power,” Turkish Journal of Computer and Mathematics Education, Vol. 13, No. 3, pp. 905–913, 2022, https://doi.org/10.17762/turcomat.v13i03.13186
-
Atef Abd El-Hay and A. Elrokh, “Total cordial labeling of corona product of paths and second power of fan graph,” Turkish Journal of Computer and Mathematics Education (TURCOMAT), Vol. 13, No. 3, pp. 681–690, 2022, https://doi.org/10.17762/turcomat.v13i03.13097
-
A. Elrokh, M. M. A. Al-Shamiri, and A. Abd El-Hay, “A novel radio geometric mean algorithm for a graph,” Symmetry, Vol. 15, No. 3, p. 570, Feb. 2023, https://doi.org/10.3390/sym15030570
-
S. Nada, A. Elrokh, and Atef Abd El-Hay, “On singed product cordial of cone graph and its second power.,” Turkish Journal of Computer and Mathematics Education (TURCOMAT), Vol. 13, No. 3, pp. 597–606, 2022, https://doi.org/10.17762/turcomat.v13i03.13070
-
A. Elrokh, M. A. Al-Shamiri, and A. Abd El-Hay, “A novel problem for solving cordial labeling of corona product between path and third order of cone graphs,” Turkish Journal of Computer and Mathematics Education (TURCOMAT), Vol. 13, No. 3, pp. 970–986, 2022, https://doi.org/10.17762/turcomat.v13i03.13219
-
A. Abd El-Hay and A. Rabie, “Signed product cordial labeling of corona product between paths and second power of fan graphs,” Italian Journal of Pure and Applied Mathematics, Vol. 48, pp. 287–294, 2022.
About this article
The authors extend their appreciation to Prof. Khalid A. Alsatami, Department of Mathematics, College of Science, Qassim University, Buraydah, KSA for supporting this work. The Researchers would like to thank the Deanship of Graduate Studies and Scientific Research at Qassim University for financial support (QU-APC-2024-9/1).
The datasets generated during and/or analyzed during the current study are available from the corresponding author on reasonable request.
Khalid A. Alsatami: conceptualization, validation, data curation. Yasmin Algrawani: methodology, formal analysis, supervision. Atef Abd El-hay: software, investigation, resources, visualization, supervision.
The authors declare that they have no conflict of interest.