[BACK]
Computer Systems Science & Engineering
DOI:10.32604/csse.2021.014810
images
Article

On Edge Irregular Reflexive Labeling of Categorical Product of Two Paths

Muhammad Javed Azhar Khan1, Muhammad Ibrahim1,*and Ali Ahmad2

1Centre for Advanced Studies in Pure and Applied Mathematics, Bahauddin Zakariya University, Multan, Pakistan
2College of Computer Science and Information Technology, Jazan University, Jazan, Saudi Arabia
*Corresponding Author: Muhammad Ibrahim. Email: mibtufail@gmail.com
Received: 19 October 2020; Accepted: 13 November 2020

Abstract: Among the huge diversity of ideas that show up while studying graph theory, one that has obtained a lot of popularity is the concept of labelings of graphs. Graph labelings give valuable mathematical models for a wide scope of applications in high technologies (cryptography, astronomy, data security, various coding theory problems, communication networks, etc.). A labeling or a valuation of a graph is any mapping that sends a certain set of graph elements to a certain set of numbers subject to certain conditions. Graph labeling is a mapping of elements of the graph, i.e., vertex and/or edges to a set of numbers (usually positive integers), called labels. If the domain is the vertex-set or the edge-set, the labelings are called vertex labelings or edge labelings respectively. Similarly, if the domain is V (G)[E(G), then the labeling is called total labeling. A reflexive edge irregular k-labeling of graph introduced by Tanna et al.: A total labeling of graph such that for any two different edges ab and a'b' of the graph their weights has images and images are distinct. The smallest value of k for which such labeling exist is called the reflexive edge strength of the graph and is denoted by res(G). In this paper we have found the exact value of the reflexive edge irregularity strength of the categorical product of two paths images for any choice of images and images

Keywords: Edge irregular reflexive labeling; reflexive edge strength; categorical product of two paths

1  Introduction

The area of graph theory has experienced fast developments during the last 60 years. Among the huge diversity of concepts that appear while studying this subject one that has gained a lot of popularity is the concept of labeling of graphs with more than 1700 papers in the literature and a very complete dynamic survey by Gallian [1]. This new branch of mathematics has caught the attention of many authors and many new labeling results appear every year. This popularity is not only due to the mathematical challenges of graph labeling, but also for the wide range of its application, for instance X-ray crystallography, coding theory, radar, astronomy, circuit design, network design and communication design. In fact, Bloom et al. studied applications of graph labeling to other branches of science and it is possible to find part of this work in Bloom et al. [2] and Bloom et al. [3].

All charts discussed in this paper are simple, finite and not directed. In Chartrand et al. [4] suggest a very nice problem. Set positive integer tags from the set images to the edges of a linked graph directly with at least three in this path, so that the graph becomes sporadic. Any weight (sum of the label) on each special edge. The question is what is the base estimate for the largest images on all this unexpected task? This parameter is for the graph images is known as the irregularity strength of the images and is denoted by images. A very nice comprehensive overview on the irregularity strength is given by Lahel [5]. For more further recent results, see the papers by Amar et al. [6], Dimitz et al. [7], Gyarfas [8], and Nierhoff [9].

There is an attraction arise from these papers as, an edge irregular k-labeling defined by images such that for every two different edges images and images there weights images, where the weight of an edge images is images. If there exist such labeling for smallest value of images then it is known as the edge irregularity strength of the graph images denoted by images. The parameter and lower bound of edge irregularity strength was introduced by Ahmad et al. [10] and found the exact value of the edge irregularity strength for several families of graphs.

The total labeling of graph introduced by Bača et al. [11] by taking the domain of mapping as the union of node and links of chart to positive integers up to images This labeling of graph is called the total images labeling of the chart images if for every two different links images and images of images one has images The total edge irregularity strength denoted by images is defined as the minimum images for which images has an edge irregular total k-labeling.

Keeping in view the problem imposed in Chartrand et al. [4] is there possible to find such labeling of the graph for a distinct degree. It seems to be impossible to construct a chart in which every node has a unique degree for a simple chart; however, it is possible for multigraphs (graphs in which we allow loops or multiple edges between the adjacent vertices). The question then became: What is the smallest number of parallel edges between two vertices required to ensure that the graph display vertex irregularity? This problem is equivalent to the labeling problem as described at the beginning of this section.

Using both Chartrand et al. [4] and Ahmad et al. [10] as motivation, in Ryan et al. [12], the authors decreed that the vertex labels should represent loops at the vertex. The consequence was two-fold; first, each vertex label was required to be an even integer, since each loop added two to the vertex degree; and second, unlike in total irregular labeling, the label 0 was permitted as representing a loopless vertex. Edges continued to be labelled by integers from one to images.

Thus, for a graph images, in Ryan et al. [12,13] are defined labelings images and images, and then, labeling images is a total k-labeling of images defined such that images if images and images if images, where images The total k-labeling images is called an edge irregular reflexive k-labeling of the graph images if for every two different edges images and images of images, one has images. The smallest value of images for which such labeling exists is called the reflexive edge irregularity strength of the graph images and is denoted by images In Ivanco et al. [14] purposed the following. Any graph images with maximum degree images other than images satisfies

images

In term of images, Ryan et al. [12] purpose the following: Any graph images with maximum degree images satisfies

images

where images for images and zero otherwise.

2  Constructing an Edge Irregular Reflexive Labeling

Let us recall the following lemma proven in Ryan et al. [12]. For every graph images,

images

From the above lemma it is noted that the minimum weight under images of a link is one and the minimum of the maximal weight of a link is equal to the number of edges/links of the graph. Further the labeling of a link can be obtained as the sum of three numbers in which at least two must be even.

In this paper, we investigate the images for the categorical product of two paths images and images for images.

3  Categorical Products of Two Paths

As far as the category of graphs and full graph homomorphisms is concern, the categorical product was introduced by Culik et al. [15] and called it as the cardinal product. After then it was defined by Weichsel [16] and name it as the Kronecker product and studies the connectedness of products of finitely many factors. Stephen et al. [17] were the first to who called the cardinal product as a categorical product. Moreover, the categorical product was extensively studied many researchers in the history of graph labeling. Ahmad et al. [18] found the total edge irregularity strength for a categorical product of two paths. Ahmad et al. [19] find the edge irregular total labeling for categorical product of two cycles. Victor et al. [20] studied the categorical product of two s-valued graphs. For the definition of categorical product of two graphs we refer [18].

Theorem 1: Let images and images be positive integers and images be the categorical product of two paths then

images

Proof. Since images has images edges. Therefore, from Lemma 2 we get

images

Next, we will show that

images

For this we define a images-labeling on images as follows:

images

images

images

The weights of the edges are given as under:

images

images

Observe that the weights of all the links receive distinct values. So, images is an edge irregular reflexive labeling of images for images. As required:

Theorem 2: Let images and images be positive integers and images be the categorical product of two paths images and images then

images

Proof. Since images has images edges. Therefore, from Lemma 2 we get

images

Next, we will show that

images

For this we define a images-labeling on images as follows:

images

images

images

The weights of reflexive edges are given as under:

images

images

Observe that the weights of all the links receive distinct values. So, images is an edge irregular reflexive labeling of images for images. As required:

Theorem 3: Let for all images and images be positive integers and images be the categorical product of two paths images and images then

images

Proof. Since images has images edges. Therefore, from Lemma 2 we get

images

Next, we will show that

images

For this we define a images-labeling on images as follow:

images

images

images

The weights of reflexive edges are given as under:

images

images

Observe that the weights of all the links receive distinct values. So, images is an edge irregular reflexive labeling of images for images and images. As required.

4  Conclusion

In this paper we have found the exact value of the reflexive edge irregularity strength of the categorical product of two paths images for any choice of images and images In future we are interested to found the reflexive edge irregularity strength of some grid related graphs.

Funding Statement: The authors received no specific funding for this study.

Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.

References

  1.  1.  J. A. Gallian. (2019). “A dynamic survey of graph labeling,” Electronic Journal of Combinatorics, vol. 19, DS6, . [Online]. Available: http://www.combinatorics.org/surveys/ds6.pdf.
  2.  2.  G. S. Bloom and S. W. Golomb. (1977). “Applications of numbered undirected graphs,” in Proc. IEEE, vol. 65, no. 4, pp. 562–570.
  3.  3.  G. S. Bloom and S. W. Golomb. (1978). “Numbered complete graphs, unusual rules, and assorted applications,” in Theory and Applications of Graphs, Lecture Notes in Mathematics, Springer-Verlag, vol. 642, pp. 53–65.
  4.  4.  G. Chartrand, M. S. Jacobson, J. Lehel, O. R. Oellermann, S. Ruiz et al. (1988). , “Irregular networks,” Congressus Numerantium, vol. 64, pp. 187–192.
  5.  5.  J. Lahel. (1991). “Facts and quests on degree irregular assignment,” in Graph Theory, Combinatorics and Applications, New York, NY, USA: Wiley, pp. 765–782.
  6.  6.  D. Amar and O. Togni. (1998). “On irregular strenght of trees,” Discrete Mathematics, vol. 190, no. 1–3, pp. 15–38.
  7.  7.  J. H. Dimitz, D. K. Garnick and A. Gyárfás, “On the irregularity strength of the m × n grid,” Journal Graph Theory, vol. 16, no. 4, pp. 355–374.
  8.  8.  A. Gyárfás, “The irregularity strength of Kmm 4 for odd m,” Discrete Mathematics, vol. 71, pp. 273–274, 1998.
  9.  9.  T. Nierhoff. (2000). “A tight bound on the irregularity strength of graphs,” SIAM Journal on Discrete Mathematics, vol. 13, no. 3, pp. 313–323.
  10. 10. A. Ahmad, O. Al Mushayt and M. Baa. (2014). “On edge irregularity strength of graphs,” Applied Mathematics and Computation, vol. 243, pp. 607–610.
  11. 11. M. Bača, S. Jendrolˇ, M. Miller and J. Ryan. (2007). “On irregular total labellings,” Discrete Mathematics, vol. 307, no. 11–12, pp. 1378–1388.
  12. 12. J. Ryan, B. Munasinghe and D. Tanna. (2017). “Reflexive irregular labeling,”.
  13. 13. M. Bača, M. Irfan, J. Ryan, A. Semaničová-Feňovčíková, D. Tanna et al. (2019). , “Note On reflexive irregular edge labelings of graphs,” AKCE International Journal of Graphs and Combinatorics, vol. 16, no. 2, pp. 145–157.
  14. 14. J. Ivančo and S. Jendrolˇ. (2006). “Total edge irregularity strength of trees,” Discussiones Mathematicae Graph Theory, vol. 26, no. 3, pp. 449–456.
  15. 15. K. Culik. (1958). “Zur Thorie der Graphen,” Casopis Pest. Mat., vol. 83, pp. 133–155.
  16. 16. P. M. Weichsel. (1962). “The Kronecker product of graphs,” in Proc. of the American Mathematical Society, vol. 18, no. 1, pp. 47–52.
  17. 17. S. T. Hedetniemi. (1965). “Homomorphisms of graphs,” University of Michigan Technical Report 03105-42-T, December, it is stated there that “the complete report is available in the major Navy technical libraries and can be obtained from the Defense Documentation Center”.
  18. 18. A. Ahmad and M. Bača. (2014). “On total edge irregularity strength of a categorical product of two paths,” Ars Combinatoria, vol. 114, pp. 203–212.
  19. 19. A. Ahmad, M. Bača and M. K. Siddiqui. (2014). “On edge irregular total labeling of categorical product of two cycles,” Theory of Computing Systems, vol. 54, no. 1, pp. 1–12.
  20. 20. P. Victor and M. Chandramouleeswaran. (2018). “Categorical product of two s-valued graphs,” Ars Mathematica Contemporanea, vol. 15, no. 1, pp. 113–126.
images This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.