Cyclic Cordial Labeling for the Lemniscate Graphs and Their Second Powers

Abstract

A lemniscate graph, usually denoted by $L_{n,m}$, is defined as a union of two cycles $C_n$ and $C_m$ that share a common vertex. A simple graph is called cyclic group cordial if we can provide a three elements’ cyclic group labeling satisfying certain conditions. The purpose of this paper is to study the cyclic cordiality of $L_{n,m}$ and their second powers $L_{n,m}^2$. Our verification goes through by using the concept of finite cyclic groups.

This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.

1. Introduction

The core of the abstract algebra subject is the notion of groups. A cyclic group usually denoted by $Z_{n}Z/nZ$ is a group generated by a single element, which is called a generator of this group. It is known that each finite cyclic group of order n is isomorphic to $Z_n$ and the abelian group of integers modulo n. All cyclic groups are abelian and furthermore, every finitely generated abelian group can be expressed as a direct product of cyclic groups [1].

Graphs are mathematical structures used to model pairwise relations between objects. This field of study is known as graph theory and has numerous applications across various disciplines, including computer science, engineering, and other branches of science. Within a computer, a graph can be represented using an adjacency matrix. Graph labeling involves assigning labels, typically represented by integers, to the edges and/or vertices of a graph. Two notable types of labeling are graceful and harmonious labeling. Graceful labeling was introduced by Rose [2], while harmonious labeling was first studied by Graham and Sloane [3]. Another significant type of labeling, which is a less strict version of both graceful and harmonious labeling, is called cordial labeling, introduced by Cahit [4]. Following his work, various studies on different types of labeling have been conducted. Cahit investigates the cordial conditions on 3-equitability of several families of graphs such as cycles [5]. Various types of cordial labeling were developed such as prime cordial labeling, total cordial labeling, product cordial labeling, and so on. In 2014, Vaidya and Shah found a way to construct a larger prime cordial graph using the given prime cordial graphs. In addition, we investigated the prime cordial labeling for double fan and degree splitting graphs of the path as well as Bistar. Moreover, they proved that the graph gained by duplication of an edge in wheel $W_n$ admits prime cordial labeling [6], Inayah et al. in 2022 studied the total product and total edge product cordial labeling for dragonfly graph ${\text{Dg}}_n$, defined generalized dragonfly graph, and found product cordial and total product cordial labeling for this family of graphs [7]. There are many types of graphs that formed from the operation on graphs such as rainbow graphs [8], friendship graphs, trees [9], and lemniscate graphs; the second power of lemniscate graphs is defined as the union of two-second power cyclic graphs, $C_n^2$ and $C_m^2$, sharing a common vertex.

In this paper, we consider only finite simple connected graphs. Let $G=V,E$ be a graph, where V is the set of its vertices and E is the set of its edges. A bijection $f:V⟶Z_3$ is a vertex labeling. Let us use the notation $i,f,g$, where i is the identity element of the cyclic group $Z_3$. Considering the multiplicative notation, the cyclic group is defined as shown in Table 1.

Table 1

The multiplicative notation of a cyclic group.

∗	i	f	$g$
i	i	f	$g$
f	f	$g$	i
$g$	$g$	i	f

An induced edge labeling $f^{\mathrm{\ast }}:E⟶Z_3$ is defined as follows: if $e\in E$ with end vertices u and $v$, then $f^{\mathrm{\ast }}e=fu+fv\mathrm{mod}3$. A bijection $f$ is called cyclic cordial of $G$ if the following two conditions are satisfied for $p,q\in i,g,f$ and $p\ne q$:

1. $v_p-v_q\le 1$

2. $e_p-e_q\le 1,$

  where $v_p$ and $v_q$ denote the number of vertices labeled by $p$ and $q$, respectively. Also, $e_p$ and $e_q$ denote the corresponding number of edges labeled by $p$ and $q$, respectively. The graph is called cyclic cordial if it admits the cyclic cordial labeling conditions. Our aim here is to study and investigate the cyclic cordiality labeling of the lemniscate graphs and their second powers.

2. Terminologies and Notations

At the lemniscate graph $L_{n,m}$, we let $x_j$ and $a_j$ denote the number of vertices and edges labeling of the cycle $C_n$, and we let $y_j$ and $b_j$ be the corresponding quantities for the cycle $C_m$, in a way that we consider the common vertex labeling belongs to the labeling of $C_n$. Then, one can see that $v_p-v_q=x_p-x_q+y_p-y_q$ and $e_p-e_q=a_p-a_q+b_p-b_q$, where $p\ne q$. The labeling of $L_{n,m}$ and $L_{n,m}^2$ are denoted by $A;B$, where the labeling $A$ is given to $C_n\text{\hspace{0.17em}or}{C}_n^2$ and the labeling $B$ is given to $C_m\text{\hspace{0.17em}or}{C}_m^2$. For this purpose, each cycle is label separately, and as we mentioned, the labeling of the common vertex is a part of the first cycle. The labeling of the second cycle starts after the common vertex.

Let us move to the detailed results.

3. The Cyclic Cordiality of Lemniscate Graphs

Theorem 1.

Every lemniscate graph, $L_{n,m},n,m\ge 3$, is cyclic cordial. To prove it, we need to go through the following three lemmas.

Lemma 1.

If $n\equiv 0\mathrm{mod}3$, then $L_{n,m}$ is a cyclic cordial.

Proof 1.

Suppose that $n=3r$, then the following cases for $m$ will be examined:

i. If $\mathrm{m}\equiv 0\mathrm{mod}3$. Then, the labeling $i,f,g,\dots ;i,f,g,\dots i,f$ will be chosen for the vertices of $L_{n,m}$. So, $x_f=x_g=x_i=n/3,y_i=y_f=m/3,y_g=m/3-1,a_i=a_f=a_g=n/3$, and $b_i=b_f=b_g=m/3$. Then, we have $v_f-v_g=v_g-v_i=1$, $v_i-v_f=0$ and $e_g-e_i=e_f-e_g=e_i-e_f=0$. So, the cyclic cordiality conditions hold. As an example, Figure 1 illustrates $L_{3.3}$.

ii. If $\mathrm{m}\equiv 1\mathrm{mod}3$, then we can choose the labeling $i,f,g,\dots ;i,f,g,\dots$ for the vertices of $L_{n,m}$. Therefore, $x_f=x_g=x_i=n/3,y_i=y_f=y_g=m-1/3,a_i=a_f=a_g=n/3$, and $b_f=m-1/3+1,b_i=b_g=m-1/3$. Then, $v_f-v_g=v_g-v_i=v_i-v_f=0$ and $e_g-e_i=0,e_f-e_g=e_i-e_f=1$. Hence, the cyclic cordiality conditions are valid.

iii. If $m\equiv 2\mathrm{mod}3$, then the labeling $i,fi,f,g,\dots i;f,g,i,\dots g$ will be chosen for the vertices of $L_{n,m}$. Then, $x_f=n/3,x_g={n/3-1,x}_i=n/3+1,y_i=y_f=m-2/3{,y}_g=m-2/3+1,a_i=n/3,a_f=n/3+1,a_g=n/3-1$, and $b_f=b_i=m-2/3,b_g=m-2/3+1$. Then, $v_f-v_g=0,$$v_g-v_i=$$v_i-v_f=1$ and $e_g-e_f=0,e_i-e_g=e_i-e_f=1$. So, the cyclic cordiality conditions hold, and hence the lemma follows. As an example, Figure 2 illustrates $L_{3.5}$.

[figure(s) omitted; refer to PDF]

Lemma 2.

If $n\equiv 1\mathrm{mod}3$, then $L_{n,m}$ is cyclic cordial.

Proof 2.

Let $n=3r+1$, then similar to the proof of Lemma 1, we study the following three cases for $m$:

i. If $m\equiv 0\mathrm{mod}3$ , then by Lemma 1 (Case [ii]), and the fact that $L_{n,m}\cong L_{m,n}$, we have that $L_{3r+1,0\mathrm{mod}3}$ is cyclic cordial.

ii. If $m\equiv 1\mathrm{mod}3$, then the labeling $i,f,g,..i;g,i,f,\dots$ is chosen to label the vertices of $L_{1\mathrm{mod}3,1\mathrm{mod}3}.$ So, $x_f=x_g=n-1/3,x_i=n-1/3+1,y_i=y_f=y_g=m-1/3,a_i=n-1/3+1,a_f=a_g=n-1/3$, and $b_i=b_f=b_g=m-1/3$. Then, $v_f-v_g=v_g-v_i=v_i-v_f=0$ and $e_f-e_g=0,e_g-e_i=e_i-e_f=1$. Hence, the cyclic cordiality labeling conditions hold.

iii. If $m\equiv 2\mathrm{mod}3$, then one can choose the labeling $if,i,g,\dots ;i,f,g,..f$ for the vertices of $L_{n,m}$. Therefore, $x_f=x_g=n-1/3,x_i=n-1/3+1,y_i=y_g=m-2/3,y_f=m-2/3+1,a_i=n-1/3-1,a_f=a_g=n-1/3+1$, and $b_f=m-2/3{+2,b}_i=b_g=m-2/3$. Then, $v_f-v_g=0,$$v_g-v_i=v_i-v_f=1$ and, $e_g-e_f=0,e_i-e_g=e_i-e_f=1$. Hence, cyclic cordiality conditions hold and the lemma follows.

Lemma 3.

If $n\equiv 2\mathrm{mod}3$, then $L_{n,m}$ is cyclic cordial.

Proof 3.

It is enough to study the case for $m\equiv 2\mathrm{mod}3.\text{\hspace{0.17em}Let\hspace{0.17em}}n=m\equiv 2\mathrm{mod}3.$

The labeling $if,i,g,\dots i;f,gi,f,g,\dots f,g$ is chosen for the vertices of $L_{2\mathrm{mod}3,2\mathrm{mod}3}.$ Then, $x_f=x_g=n-2/3,x_i=n-2/3+2,y_g=y_f=m-2/3+1,y_i=m-2/3-1,a_i=n-2/3,a_f=a_g=n-2/3+1$, and $b_i=m-2/3+2,{b_f=b}_g=m-2/3$. Hence, cyclic cordiality conditions hold and the lemma follows.

Proof of Theorem 1.

This is a direct consequence of the above three lemmas.

4. The Cyclic Group Cordial Labeling for the Second Power of the Lemniscate Graphs

Theorem 2.

Every second power of lemniscate graphs, $L_{n,m}^2$, $n,m$ ≥ $3$ is cyclic cordial.

To achieve this result, we first need to prove the following special case for $n=3$.

Lemma 4.

If $n=3$, then $L_{3,m}^2$ is cyclic cordial.

Proof 4.

Suppose that $n=3,$ the following cases for $m$ will be examined:

i. If $m\equiv 0\mathrm{mod}3$, then the labeling $i,f,g;i,f,g,\dots i,f$ is chosen to label the vertices of $L_{3,0\mathrm{mod}3}^2.$ So, $x_f=x_g=x_i=1,y_i=y_f=m/3,y_g=m/3-1,{a_i=a}_f=a_g=1$, and $b_i=2m/3,b_f=b_g=2m/3-1$. Then, we have $v_f-v_g=v_g-v_i=1,$$v_i-v_f=0$ and $e_g-e_f=e_i-e_g=1,e_i-e_f=0$. Therefore, the cyclic cordial labeling conditions hold. As an example, Figure 3 illustrates $L_{3.6}^2$.

ii. If $m\equiv 1\mathrm{mod}3$, then one can choose the labeling $i,f,g;i,f,g,\dots$ for the vertices of $L_{3,1\mathrm{mod}3}^2.$ Therefore, $x_f=x_g=x_i=1,y_i=y_f=y_g=m/3,a_i=a_f=a_g=1$, and $b_i=b_g=b_f=2m-1/3$. Then, $L_{3,m+1}^2$ is cyclic cordial.

iii. If $m\equiv 2\mathrm{mod}3$, one can label the vertices by $i,g,f;i,f,g,\dots i$ for $L_{3,2\mathrm{mod}3}^2.$ So, $x_f=x_g=x_i=1,y_i=m/3+1,y_f=y_g=m-2/3,a_i=a_f=a_g=1$, and $b_i=b_g=2m-2/3+1,b_f=2m-2/3$. It follows that $v_f-v_g=v_f-v_i=1,$$v_i-v_g=0$ and $e_g-e_f=e_i-e_f=1,e_i-e_g=0$. Then, $L_{3,m+2}^2$ is cyclic cordial. Hence, cyclic cordiality conditions of these special cases hold, and the lemma follows.

[figure(s) omitted; refer to PDF]

For general cases, we study the following lemmas.

Lemma 5.

If $n\equiv 0\mathrm{mod}3$, n > 3, then $L_{n,m}^2$, where $m\ge 3$ is cyclic cordial.

Proof 5.

Suppose that $n=3r,$ the following cases for $m$ will be examined:

i. If $m\equiv 0\mathrm{mod}3$, the labeling $i,f,g,\dots ;i,f,g,\dots i,f$ will be chosen for the vertices of $L_{n,m}^2$. Therefore, $x_f=x_g=x_i=n/3,y_i=y_f=m/3,y_g=m/3-1,a_i=a_f=a_g=n/3$, and $b_i=2m/3,b_f=b_g=2m/3-1$. It follows that $v_f-v_g=v_f-v_i=v_i-v_g=0$ and $e_g-e_f=0,e_i-e_f=e_i-e_g=1$. Hence, then $L_{n,m}^2$ is cyclic cordial.

ii. If $m\equiv 1\mathrm{mod}3$, then one can choose $\text{the\hspace{0.17em}labeling\hspace{0.17em}}i,f,g,\dots ;i,f,g,\dots$ for the vertices of $L_{n,m}^2$. Then, $x_f=x_g=x_i=n/3,y_i=y_f=y_g=m-1/3,a_i=a_f=2n/3-1,a_g=2n/3$, and $b_i=b_g=b_f=2m/3$. It follows that $v_f-v_g=v_f-v_i=v_i-v_g=0$ and $e_g-e_f=e_i-e_g=1,e_i-e_f=0$. Hence, cyclic cordiality conditions hold.

iii. If $m\equiv 2\mathrm{mod}3$, then we can choose the labeling $i,f,g,\dots ;i,f,g,\dots g$ for the vertices of $L_{n,m}^2$. So, $x_f=x_g=x_i=n/3,y_i=y_f=m/3,y_g=m/3+1,a_i=a_f=a_g=n/3$, and $b_i=b_f=2m-2/3+1,b_g=2m-2/3.$ Then, $v_f-v_i=0,v_f-v_g=$$v_i-v_g=1$ and $e_g-e_f=e_i-e_g=e_i-e_f=0$. Hence, cyclic cordiality conditions are valid, and the lemma follows. As an example, Figure 4 illustrates $L_{6.5}^2$.

[figure(s) omitted; refer to PDF]

Lemma 6.

If $n\equiv 1\mathrm{mod}3,$ then $L_{n,m}^2$ is cyclic cordial.

Proof 6.

Suppose that $n=3r+1,$ the following cases for $m$ will be examined:

i. If $m\equiv 1\mathrm{mod}3$, then we can choose the labeling $i,f,g,\dots i;i,f,g,\dots$ for the vertices of $L_{n,m}^2$. So, $x_f=x_g=n-1/3,x_i=n-1/3+1,y_i=y_f=y_g=m-1/3,a_i=a_f=a_g=2n-1/3,$ and $b_i=b_f=b_g=2m-1/3$. Then, $v_f-v_g=0,v_f-v_i=$$v_i-v_g=1$ and $e_g-e_f=e_i-e_g=e_i-e_f=0$. Hence, cyclic cordiality conditions hold. As an example, Figure 5 illustrates $L_{4.4}^2$.

ii. If $m\equiv 2\mathrm{mod}3$, then the $i,f,g,\dots i;i,f,g,\dots f$ will be chosen for the vertices of $L_{n.m}^2$. Therefore, $x_f=x_g=n-1/3,x_i=n-1/3+1,y_i=y_g=m-2/3,y_f=m-2/3+1,a_i=a_f=a_g=2n-1/3$, and $b_i=b_f=2m-2/3+2,b_g=2m-2/3$. Then, $v_f-v_g=v_g-v_i=$ 1, $v_i-v_f=0$, and $e_g-e_f=e_i-e_g=1,e_i-e_f=0$. Hence, cyclic cordiality conditions are valid, and the lemma follows.

[figure(s) omitted; refer to PDF]

Lemma 7.

If $n\equiv 2\mathrm{mod}3$, then $L_{n,m}^2$ is cyclic cordial.

Proof 7.

Suppose that $n=3r+2$ . We need only to examine the following case.

Let $m\equiv 2\mathrm{mod}3$, then we choose the labeling $i,f,g,\dots f,i;i,f,g,\dots g$ for the vertices of $L_{n,m}^2$. So, $x_f=x_i=n-2/3+1,x_g=n-2/3,y_i=y_f=m-2/3,y_g=m-2/3+1,a_i=a_g=2n-2/3+1,$$a_f=2n-2/3$, and $b_i=b_f=2m-2/3+1,b_g=2m-2/3$. It follows that $v_f-v_g=v_f-v_i=v_i-v_g=0$ and $e_g-e_f=0,e_i-e_g=e_i-e_f=1$. Therefore, cyclic cordiality conditions are valid, and the lemma follows.

Proof of the Theorem 2.

It is a direct consequence of the forgoing four lemmas.

5. Conclusion

The cyclic cordial labeling is an important connection notion between group theory and graph theory. Here, we use the cyclic group $Z_3$ for labeling the lemniscate graphs and their second powers and show that these graphs have cyclic cordial labeling.

Author Contributions

All authors contributed equally and significantly to writing this article. All authors read and approved the final manuscript.

Funding

This research was funded by King Khalid University through the Large Groups Project under grant number: R. G. P. 2/206/46.

Acknowledgments

The authors extend their appreciation to the Deanship of Scientific Research at King Khalid University for funding this work through the Large Groups Project under grant number: R. G. P. 2/206/46.

References

[1] J. Fraleigh, A First Course in Abstract Algebra, 2014.

[2] A. Rose, "On Certain Valuations of Vertices of a Graph: Theory of Graphs," Procedure for Internet, pp. 349-355, .

[3] R. Graham, N. Sloane, "On Additive Bases and Harmonious Graphs," SIAM Journal on Algebraic and Discrete Methods, vol. 1 no. 4, pp. 382-404, DOI: 10.1137/0601045, 1980.

[4] I. Cahit, "Cordial Graphs-A Weaker Version of Graceful and Harmonious Graphs," Ars Combinatoria, vol. 23, pp. 201-207, 1987.

[5] I. Cahit, "On Cordial and 3-equitable Labelings of Graphs. Util," Mathesis, vol. 37, pp. 189-198, 1990.

[6] S. K. Vaidya, N. H. Shah, "Some New Results on Prime Cordial Labeling," ISRN Combinatorics, vol. 2014,DOI: 10.1155/2014/607018, 2014.

[7] N. Inayah, A. Erfanian, M. Korivand, "Total Product and Total Edge Product Cordial Labelings of Dragonfly Graph (Dg n )," Journal of Mathematics, vol. 2022 no. 1,DOI: 10.1155/2022/3728344, 2022.

[8] B. J. Septory, L. Susilowaty, V. Lokesha, V. Lokehsa, G. Nagamani, "On the Study of Rainbow Antimagic Connection Number of Corona Product of Graphs," European Journal of Pure and Applied Mathematics, vol. 16 no. 1, pp. 271-285, DOI: 10.29020/nybg.ejpam.v16i1.4520, 2023.