A study on the varieties of equivalent cordial labeling graphs

1.   Introduction

In recent years, graph theory has seen the development of several captivating research areas, with graph labeling standing out as a particularly dynamic and versatile field. Graph labeling has diverse applications across multiple disciplines, including communication networks, database management, coding theory, and more. A graph labeling involves assigning integers to the vertices or edges, or both, under specific conditions. Most of the references in the literature attribute the beginning of graph labeling to the work of Rosa ^[1]. Various labeling techniques have been thoroughly explored, such as graceful labeling by ^[2] and odd graceful labeling by ^[3]. Odd harmonious labeling ^[4], radio labeling by ^[5], mean labeling by ^[6], and so on. Motivated by this concept, several researchers have studied this topic, and relevant results have been published in many journals and proceedings, among others. An up-to-date dynamic survey of graph labeling is regularly published and maintained by Gallian ^[7].

The concept of cordial labeling was introduced by Cahit ^[8] in 1987 as a weaker version of graceful and harmonious. In 2011, Babujee et al. ^[9] introduced the concept of signed product cordial labeling. Moreover, in 2022, motivated by cordial labeling, Elrokh et al. ^[10] defined the concept of logical cordial labeling. In 2023, Elrokh et al. ^[11,12] introduced the notion of cubic roots and permuted cordial labeling.

The cordial labeling scheme is important. While cordial labeling primarily serves as a theoretical construct in graph theory, it has potential applications in areas such as network design, error-correcting codes, and cryptography. In particular, cordial labelings could be useful in designing efficient communication protocols where balancing two types of nodes (positive and negative) is essential. There are different types of cordial labeling that have been introduced, like cordial labeling, signed product cordial labeling, logically cordial labeling, permuted cordial labeling, and cubic roots cordial labeling. The key idea of our paper is to challenge a longstanding assumption in the literature that the three labeling schemes (cordial, signed, and logically cordial) are independent. Our results demonstrate that, in fact, these structures are equivalent, not independent, and also prove that the permuted cordial labeling and cubic roots cordial labeling coincide.

The remainder of the paper is structured as follows: Section 2 provides a summary of definitions pertinent to the current investigations. In Section 3, we demonstrate the equivalence between cordial, signed product cordial, and logical cordial labelings. Also, we have proven that the permuted cordial labeling and cubic roots cordial labeling coincide. Section 4 presents and discusses our results and several examples aimed at investigating the cordiality behavior of various families of standard graphs. Lastly, the paper concludes with a final section.

2.   Terminology and related work

In this section, we shall present basic notation and terminologies that are will frequently use in our main results.

Let

be a graph, where $V$ is the set of its vertices and $E$ is the set of its edges. For the sake of consistency, we assume throughout that $G$ is finite, simple, and undirected. The cordial labeling started. Consider a function

and the induced edge labeling

is given by

where

$f$ is called a cordial labeling of $G$ if the number of vertices labeled 0 and the number of vertices labeled 1 differ by at most 1, and the number of edges labeled 0 and the number of edges labeled 1 differ at most by 1. Cordial labeling uses only labels 0 and 1 and the induced edge label $(f(u)+f(v))(\bmod 2)$, which of course equals $|f(u)-f(v)|$. Because arithmetic modulo 2 is an integral part of computer science, cordial labeling has close connections with that field. Many researchers have been interested in cordial labeling of different kinds of graphs.

In ^[9] the concept of signed product cordial labeling was introduced. Babujee and Loganathan define a graph is a signed product cordial if it is possible to label the edges and vertices with the numbers from the set $\{-1, 1\}$ in such a way as follows.

Definition 2.1. ^[9] Let

be a graph and let

be a vertex labeling of graph $G$, with induced edge labeling

defined by

where

$f$ is called a signed product cordial labeling if

and

where $V_{f}(-1)$ is the number of vertices labeled with $-1, V_{f}(1)$ is the number of vertices labeled with 1, $E_{f^{*}}(-1)$ is the number of edges labeled with $-1$, and $E_{f^{*}}(1)$ is the number of edges labeled with 1. A graph $G$ is signed product cordial if it admits signed product cordial labeling.

In ^[10], a new concept of cordial labeling was introduced, recalling logical cordial labeling.

Definition 2.2. ^[10] Let

be a graph and let

be a vertex labeling of graph $G$, with induced edge labeling

defined by

where

$f$ is called logical cordial labeling if

and

where $V_{f}(0)$ is the number of vertices labeled with $0, V_{f}(1)$ is the number of vertices labeled with 1, $E_{f^{*}}(0)$ is the number of edges labeled with 0, and $E_{f^{*}}(1)$ is the number of edges labeled with 1. A graph $G$ is logically cordial if it admits logical cordial labeling.

In ^[11], a new concept of cordial labeling was introduced, specifically recalling cubic roots cordial labeling.

Definition 2.3. ^[11] Let

be a graph and let

be a vertex labeling of graph $G$, where $1, \omega, \omega^{2}$ are the cube roots of a unit, with induced edge labeling

defined by:

is called a cubic roots cordial labeling if

and

$x \neq y$ and $x, y \in\left\{1, \omega, \omega^{2}\right\}$, where $V_{f}(x)$ is the number of vertices labeled with $x$, $V_{f}(y)$ is the number of vertices labeled with $y, E_{f^{*}}(x)$ is the number of edges labeled with $x$, and $E_{f^{*}}(y)$ is the number of edges labeled with $y$. A graph $G$ is cubic roots cordial if it admits cubic roots cordial labeling.

In ^[12], a new concept of cordial labeling was introduced, recalling permuted cordial labeling.

Definition 2.4. ^[12] Let

be a graph and let

be a vertex labeling of graph $G$, with induced edge labeling

defined by:

is called permuted cordial labeling if

and

$x \neq y$ and $x, y \in\{i, f, g\}$, where $V_{h}(x)$ is the number of vertices labeled with $x$, $V_{h}(y)$ is the number of vertices labeled with $y, E_{h^{*}}(x)$ is the number of edges labeled with $x$, and $E_{h^{*}}(y)$ is the number of edges labeled with $y$. A graph $G$ is permuted cordial if it admits permuted cordial labeling.

In ^[13], Hovey introduced $A$-cordial labeling as a generalization of cordial and harmonious, and elegant labeling. If $A$ is an abelian group, then a labeling

of the vertices of some graph $G$ induces an edge labeling on $G$; the edge $u v$ receives the label $f(u)+f(v)$. A graph $G$ is $A$-cordial if there is a vertex-labeling such that (1) the vertex label classes differ in size by at most one and (2) the induced edge label classes differ in size by at most one.

Definition 2.5. ^[13] $G$ is $A$-cordial if there is a labeling

such that for all $a, b \in \mathrm{A}$, we have:

(1) $\left|E_{f}(a)-E_{\mathrm{f}}(b)\right| \leq 1$;

(2) $\left|E_{f^{*}}(\mathrm{a})-E_{f^{*}}(\mathrm{\; b})\right| \leq 1$.

If

we will say that $G$ is $k$-cordial. Then one wants to know which graphs are $A$-cordial. Special cases of this have appeared in the literature before. Recall that $p$ and $q$ denote the number of vertices and edges of $G$:

(Ⅰ) $G$ is harmonious ^[14] if and only if $G$ is $q$-cordial.

(Ⅱ) $G$ is elegant ^[15] if and only if $G$ is $p$-cordial.

(Ⅲ) $G$ is cordial ^[8] if and only if $G$ is 2-cordial.

The problem of completely classifying $A$-cordial graphs seems to be a very hard one.

Now, it is important to delve into functions between groups that preserve the respective binary operations. This introduces the concept of a homomorphism.

Definition 2.6. ^[16] Let $\langle G_{1}, *\rangle$ and $\langle G_{2}, o\rangle$ be groups. A function

is called a homomorphism if

for all $a, b \in G$. If the homomorphism $\varphi$ is injective and surjective, $\varphi$ is called a group isomorphism.

Proposition 2.1. ^[16] Let

be two cyclic groups generated by $a$ and $b$, respectively, such that

Then there exists an isomorphism:

given by

3.   Main results

In this section, we present a formal method for determining whether two labelings defined in different terms are equivalent. Additionally, we establish the equivalence between cordial, signed product cordial, and logical cordial labelings. Furthermore, we demonstrate that graph $G$ admits a permuted cordial labeling if and only if it exhibits a cubic roots cordial labeling.

To achieve this, we redefine cordial labeling, signed product cordial labeling, and logical cordial labeling using the notion of $A$-cordial labeling and cyclic groups as follows:

Remark 3.1. Let

be a finite simple graph, we have three cases:

$(1)$ If

then in this case, $A$-cordial labeling coincides with cordial labeling.

$(2)$ If

where ($\cdot$) standard product operation, then in this case, $A$-cordial labeling coincides with signed product cordial labeling.

$(3)$ If

where $(*)$ is defined by

then in this case, $A$-cordial labeling coincides with logical cordial labeling.

We are now prepared to present a crucial result that significantly contributes to our objective.

Proposition 3.1. Let

be a graph, and $(H, +), (K, \oplus)$ be two isomorphic finite abelian groups. Then $G$ is $H$-cordial if and only if $G$ is $K$-cordial.

Proof. Since $(H, +)$ and $(K, \oplus)$ are isomorphic, there exists a group isomorphism

First, suppose that $G$ is $H$-cordial. Then there exists a function

a vertex labeling of $G$, with induced edge labeling

defined by

and satisfy the following conditions

and

for any $x, y \in H$. Now, we define new functions:

and

As illustrated below:

Note that:

Since $\varphi$ is an isomorphism, then for any $a, b \in K$, there exist unique $x, y \in H$ such that

and

Under these assumptions, we find that:

Similarly,

Further,

Similarly,

It follows from (3.1) and (3.2)

also from (3.3) and (3.4), we obtain:

Hence, $G$ is $K$-cordial.

Using similar arguments, the converse can be shown. □

Building on the preceding proposition and the fact that the groups $A_{1}$–$A_{3}$ in Remark 3.1 are finite and isomorphic, we conclude that the three labeling schemes cordial, signed product cordial, and logically cordial are equivalent. While this equivalence follows directly from prior results, we include part of the proof to emphasize the importance of these labelings, address misconceptions of their independence, and clarify the equivalence through the similarity of their elements.

Corollary 3.1. Let

be a graph, then the following labelings are equivalent:

(1) $G$ is a signed product cordial;

(2) $G$ is cordial;

(3) $G$ is logically cordial.

Proof. $(1) \Rightarrow (2)$. Suppose that $G$ is a signed product cordial. Then there exists a function

a vertex labeling of graph G, with induced edge labeling

defined by

such that:

and

Clearly, $\left(A_{1}, \oplus_{2}\right)$ and $\left(A_{2}, \cdot\right)$ are two cyclic groups of order 2 and generated by 1 and $-1$, respectively. Therefore, by using Proposition 2.1, there exists a group isomorphism:

given by

Now, we define new functions

and

As illustrated below:

defined by for all $v \in G$ :

Note that:

Clearly, we observe that:

Under these assumptions, we find that:

Note that

and

Similarly,

Further,

Similarly,

Therefore, we observe that:

and

Hence, $G$ is a cordial.

Using similar arguments, (2) $\Rightarrow$ (3) and (3) $\Rightarrow$ (1). □

The following result directly follows from the preceding outcome.

Corollary 3.2. All graphs that admit cordial labeling also possess the properties of being signed product cordial and logically cordial.

References ^[11,12] introduce the concepts of permuted cordial labeling and cubic roots cordial labeling, respectively. The following result demonstrates that these labelings are equivalent.

Theorem 3.1. Let

be a graph, then the following labelings are equivalent:

(1) $G$ is permuted cordial;

(2) $G$ is cubic roots.

Proof. Based on Proposition 3.1, we can conclude that

and

are two cyclic groups generated by $\omega$ and $f$, respectively, such that

Therefore, $(H, \cdot)$ and $(K, o)$ are two finite isomorphic abelian groups and we obtain that $G$ is $H$-cordial (permuted cordial) if and only if $G$ is $K$-cordial (cubic roots). □

The following result directly follows from the preceding outcome:

Corollary 3.3. All graphs that possess permuted cordial labeling also exhibit cubic roots cordial labeling.

4.   Examples and discussion

An intriguing observation arises from Proposition 3.1, revealing the equivalence between several new and existing results. For instance, in ^[17], the authors established that any lemniscate graph is a signed product cordial graph if and only if its size is not congruent to $2(\bmod 4)$. Furthermore, they concluded that the second power of the lemniscate graph $L_{\text {n.m }}^{2}$ is a signed product cordial for all $n \geq 3, m \geq 3$. However, a subsequent study in ^[18] demonstrated that the same graph also exhibits cordiality under the same conditions.

In ^[19], the authors concluded that the signed product cordiality of the corona between paths and the fourth power of paths is cordial for all $m, n \geq 7$, and $n = 3$ for all $m = 1$. Similarly, ^[20] confirmed that the same graph exhibits cordiality under these exact conditions.

In ^[21,22], the authors conducted experiments to evaluate the signed product cordiality and cordiality of the sum and union of the fourth powers of two paths, as well as cycles. They further analyzed the cordiality of the union of the fourth powers of two paths and cycles. Notably, the findings were consistently reproduced across different studies. This underscores the equivalence between these labelings, as revealed in this article, and highlights how new results can emerge as reinterpretations of pre-existing findings, often presented as entirely novel discoveries.

In ^[23], the authors present novel findings on signed product cordial labeling and delve into the necessary and sufficient conditions for the corona product between paths and the second power of fan graphs to exhibit signed product cordiality. However, a subsequent study in ^[24] demonstrated that the same graph also satisfies the conditions for cordiality.

Finally, extensive research has been devoted to exploring cordial labeling and signed product cordiality. The cordiality of the second power of paths and the third power of paths, as well as their associations with other graphs, was studied in ^[25,26], respectively. In ^[27], the cordiality of the join of pairs of the third power of paths was examined. According to Corollary 3.1, we can deduced that, all these graphs are admit a signed product cordial and logical cordial labeling. Moreover, ^[28] investigates the signed product cordiality of several special classes of graphs, including combs, webs, complete bipartite graphs, jewels, gears, quadrilateral snakes, and triangular snakes. In ^[29], duplicate graphs such as bistars, double stars, and triangular ladder graphs are shown to admit signed product cordial labeling. Additionally, ^[30] explores signed product cordial labeling for splitting graphs of the bull graph and star graph. As highlighted in Corollary 3.1, all these graphs also admit cordial and logical cordial labeling.

5.   Conclusions

The concepts of cordial labeling, signed product cordiality, and logical cordiality have been independently introduced by various researchers as distinct labeling schemes. In this paper, we establish the equivalence of these concepts. Specifically, we prove that a graph $G$ is cordial if and only if it is signed product cordial and if and only if it is logically cordial. Moreover, we demonstrate that a graph $G$ admits permuted cordial labeling if and only if it exhibits cubic roots cordial labeling. Through this newly discovered equivalence, we proceed to analyze the cordiality properties of several well known graphs. This highlights the fundamental equivalence between these labeling schemes, as presented in this article, and illustrates how new results can emerge from reinterpretations of existing findings, often framed as entirely novel discoveries. Future work will focus on exploring the application of these equivalences to more complex graph classes and expanding the analysis to additional labeling schemes. Additionally, we aim to investigate the computational aspects of verifying cordial labeling properties in larger and more intricate graph structures, as well as extending the findings to directed and weighted graphs.

Author contributions

M. E. Abdel-Aal: conceptualized the study, designed the study, prepared the first draft, conducted a review of the literature, reviewed draft manuscript, and finalized the manuscript; S. A. Bashammakh: designed the study, conducted the literature search, and provided funding. All authors have read and agreed to the published version of the manuscript.

Use of Generative-AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The authors sincerely thank the referees for their valuable suggestions to add a few more new results also. The authors extend sincere gratitude to Prof. Maher Zayed for his invaluable guidance, support, and constructive feedback, which significantly enhanced the quality of this article. His expertise and dedication are truly commendable.

Conflicts of interest

The authors declare that they have no conflicts of interest in this paper.