On Legendre Cordial Labeling of Some Graphs

For a simple connected graph G = (V, E), a bijective function f : V(G) → {1, 2, ..., |V|} is said to be a Legendre cordial labeling modulo p, where p is an odd prime, if the induced function f_p ∗ : E(G) → {0, 1} defined by f_p ∗ (uv) = 0 if (ω_uv/p) = −1 or ω_uv = 0, and f_p ∗(uv) = 1 if (ω_uv/p) = 1, where f (u) + f (v) ≡ ω_uv (mod p), 0 ≤ ω_uv < p, satisfies the condition e_fp * (0) − e_fp ∗ (1) ≤ 1, where e_fp ∗ (i) is the number of edges with label i (i = 0, 1). In this paper, we determined the values of n, m, and k so that the following special graphs admit a Legendre cordial labeling modulo p for an odd prime p: path graph P_n, cycle graph C_n, star graph S_n, tadpole graph T_n,m, kayak paddle graph KP_n,m,k, bistar graph B_n,m, and fan graph Fn.

Introduction

In this study, only graphs that were finite, simple, and connected were considered. A graph $G=(V,E)$ has a vertex set $V=V(G)$ and an edge set $E=E(G)$, and the cardinalities $|V|$ and $|E|$ are called the order and size of $G$, respectively. For a general reference to graph-theoretic notions, refer to [1]. Graph labeling is a concept in graph theory in which integers are assigned to vertices or edges (or both) subject to certain conditions. This topic is an active area of research with numerous applications in coding theory and communications.

In the number theory, finding solutions to certain equations or congruences (subject to certain conditions) is very important. Quadratic congruence $x^2\equiv a(\text{mod}p)$, where $p$ is an odd prime, has been studied for many years, and several properties have been established to test whether the congruence has a solution. Legendre, a French mathematician, introduced the Legendre symbol $(a/p)$ which states that if $p$ is an odd prime and $a$ is an integer relatively prime to $p$, then $(a/p)=1$ whenever $x^2\equiv a(\text{mod}p)$ has a solution; otherwise, $(a/p)=-1$. Several properties of the Legendre symbol can be found in previous studies [2], [3]. Various topics in number theory such as encryption, decryption, and the Fibonacci series, are now significant in the fields of cryptography, computer science, and engineering [4].

In 1987, Cahit [5] introduced a new graph-labeling method called cordial labeling. This graph labeling is considered a weaker version of graceful labeling and harmonious labeling. It also serves as a foundation for different topics of graph labeling, such as total product cordial labeling [6], Lucas divisor cordial labeling [7], and Fibonacci cordial labeling [8]. In fact, some topics of cordial labeling, namely, sum cordial labeling and mean cordial labeling, are utilized to study blood circulation, human anatomy, and the circulatory system [9], [10].

In this study, we introduce a new type of cordial labeling, called Legendre cordial labeling. Let $p$ be an odd prime. For a simple connected graph $G=(V,E)$ of order $n$, a bijective function $f:V(G)\to \{1,2,\dots ,n\}$ is said to be a Legendre cordial labeling modulo $p$ if the induced function $f_p^{\ast }:E(G)\to \{0,1\}$ is defined by

$$\begin{array}{r}{f}_p^{\ast }\left(uv\right)=\{\begin{array}{l}0\text{ if }\left({\omega }_{uv}/p\right)=-1\text{ or }{\omega }_{uv}=0\\ 1\text{ if }\left({\omega }_{uv}/p\right)=1\end{array}\end{array}$$

given that $f(u)+f(v)\equiv {\omega }_{uv}(\text{mod}p)$, $0\le {\omega }_{uv}<p$, satisfies the condition $|e_{f_p^{\ast }}(0)-e_{f_p^{\ast }}(1)|\le 1$, where $e_{f_p^{\ast }}(i)$ is the number of edges with label $i$ ($i=0,1$). A graph that admits a Legendre cordial labeling modulo $p$ is called a Legendre cordial graph modulo $p$.

Additionally, this new type of cordial labeling extends the traditional graph labeling methods by incorporating the Legendre symbol. In addition, this approach aims to investigate new mathematical structures in graph labeling and to explore their potential applications in real life.

Preliminaries

Definition 2.1. A path graph $P_n$ of order $n$ is a graph with vertex set $V(P_n)=\{v_1,v_2,\dots ,v_n\}$ and edge set $E(P_n)=\{v_1{v}_2,v_2{v}_3,\dots ,v_{n-1}{v}_n\}$.

Definition 2.2. A cycle graph $C_n$ of order $n$ is a graph with vertex set $V(C_n)=\{v_1,v_2,\dots ,v_n\}$ and edge set $E(C_n)=\{v_1{v}_2,v_2{v}_3,\dots ,v_{n-1}{v}_n,v_n{v}_1\}$.

Definition 2.3. A star graph $S_n$ of order $n$ is a graph obtained from vertices $v_1,v_2,\dots ,v_{n-1}$ and connects each of these vertices to a central vertex $v_n$.

Definition 2.4. A tadpole graph $T_{n,m}$ of order $n+m$ is obtained from a cycle graph $C_n$ and path graph $P_{m+1}$ where a pendant vertex (a vertex with degree 1) is a vertex of $C_n$.

Definition 2.5. A kayak paddle graph $K{P}_{n,m,k}$ of order $n+m+k$ is a graph obtained from two cycle graphs $C_n$ and $C_k$, and path graph $P_{m+2}$ for which a pendant vertex of $P_{m+2}$ is a vertex of $C_n$ and the other pendant vertex is a vertex of $C_k$.

Definition 2.6. A bistar graph $B_{n,m}$ of order $n+m$ is obtained from two star graphs $S_n$ and $S_m$ such that the central vertex of $S_n$ is adjacent to the central vertex of $S_m$.

Definition 2.7. A fan graph $F_n$ of order $n$ is obtained from path graph $P_{n-1}$ and connects each vertex of $P_{n-1}$ to a new vertex $x_0$.

Definition 2.8. Let $p$ be an odd prime and $a$ be an integer relatively prime to $p$. Then $a$ is a quadratic residue of $p$ if the quadratic congruence $x^2\equiv a(modp)$ has a solution. Otherwise, $a$ is a quadratic nonresidue of $p$. The Legendre symbol $(a/p)$ is defined as $(a/p)=1$ if $a$ is a quadratic residue of $p$; otherwise, $(a/p)=-1$.

Theorem 2.9. [3] Let $p$ be an odd prime. Then $p$ has $\frac{p-1}{2}$ quadratic residues and $\frac{p-1}{2}$ quadratic nonresidues in the set $\{1,2,\dots ,p-1\}$.

Theorem 2.10. [3] Let $p$ be an odd prime and let $a$ and $b$ be integers relatively prime to $p$. If $a\equiv b(\text{mod}p)$, then $(a/p)=(b/p)$.

Main Results

In the succeeding discussion, we denote $p$ as an odd prime.

Lemma 3.1. There exists an integer $k$, $0\le k<p$, such that $\left(\frac{p+2k\pm 1}{2}/p\right)=1$.

Proof. Define ${\theta }_k\equiv (p+2k\pm 1)/2(\text{mod}p)$, $0\le {\theta }_k<p$, for $k=1,2,\dots ,p-1.$ Let $\zeta =\{{\theta }_k:k=0,1,\dots ,p-1\}$, then $\zeta =\{0,1,\dots ,p-1\}$. According to Theorem 2.9, $p$ has $\frac{p-1}{2}$ quadratic residues in set $\zeta$. Thus, $({\theta }_k/p)=1$ for some integer $k$, $0\le k<p$. Because $\left(\frac{p+2k\pm 1}{2}/p\right)=({\theta }_k/p)$ by Theorem 2.10, there exists an integer $k$, $0\le k<p$, such that $\left(\frac{p+2k\pm 1}{2}/p\right)=1$. □

Theorem 3.2. The path graph $P_p$ is a Legendre cordial graph modulo $p$.

Proof. Let $V(P_p)=\{v_1,v_2,\dots ,v_p\}$ and define the bijective function $f:V(P_p)\to \{1,2,\dots ,p\}$ by

$$\begin{array}{r}f\left(v_i\right)=\{\begin{array}{l}i+{\displaystyle \frac{p-1}{2}}\text{ for }i=1,2,\dots ,{\displaystyle \frac{p+1}{2}}\\ i-{\displaystyle \frac{p+1}{2}}\text{ for }i={\displaystyle \frac{p+3}{2}},{\displaystyle \frac{p+5}{2}},\dots ,p.\end{array}\end{array}$$

As a consequence, for $v_i{v}_{i+1}\in E(P_p)$,

$$\begin{array}{r}f\left(v_i\right)+f\left(v_{i+1}\right)\equiv \{\begin{array}{ll}2i\left(\text{mod}p\right)& \text{ for }i=1,2,\dots ,{\displaystyle \frac{p-1}{2}}\\ (2i-p)\left(\text{mod}p\right)& \text{ for }i={\displaystyle \frac{p+1}{2}},{\displaystyle \frac{p+3}{2}},\dots ,p-1.\end{array}\end{array}$$

In view of this labeling, let

$$\begin{array}{r}\alpha =\{\xi :f(v_i)+f(v_{i+1})\equiv \xi (\text{mod}p),0<\xi <p,i=1,2,\dots ,p-1\}.\end{array}$$

Thus, $\alpha =\{1,2,\dots ,p-1\}$ and by Theorem 2.9, $p$ has $\frac{p-1}{2}$ quadratic residues and $\frac{p-1}{2}$ quadratic nonresidues in set $\alpha$. Hence, $e_{f_p^{\ast }}(0)=e_{f_p^{\ast }}(1)=\frac{p-1}{2}$. Therefore, $|e_{f_p^{\ast }}(0)-e_{f_p^{\ast }}(1)|=0$ and it follows that $P_p$ admits a Legendre cordial labeling modulo $p$. □

Example 3.3. Fig. 1 presents the Legendre cordial labeling modulo $p$ of the path graph $P_p$, specifically illustrated for the case $p=7$.

Fig. 1. Legendre cordial labeling modulo $7$ of $P_7$.

Theorem 3.4. The cycle graph $C_p$ is a Legendre cordial graph modulo $p$.

Proof. Let $V(C_p)=\{v_1,v_2,\dots ,v_p\}$ and suppose that $f:V(C_p)\to \{1,2,\dots ,p\}$ is a bijective function defined by $f(v_i)=i$ for $i=1,2,\dots ,p$. Consequently, for $v_i{v}_{i+1}\in E(C_p)$,

$$\begin{array}{r}f\left(v_i\right)+f\left(v_{i+1}\right)\equiv \{\begin{array}{ll}(2i+1)\left(\text{mod}p\right)& \text{ for }i=1,2,\dots ,{\displaystyle \frac{p-3}{2}}\\ 0\left(\text{mod}p\right)& \text{ for }i={\displaystyle \frac{p-1}{2}}\\ (2i-p+1)\left(\text{mod}p\right)& \text{ for }i={\displaystyle \frac{p+1}{2}},{\displaystyle \frac{p+3}{2}},\dots ,p,\end{array}\end{array}$$

and for $v_1{v}_p\in E(C_p)$, $f(v_1)+f(v_p)\equiv 1(\text{mod}p)$. In view of the above labeling, suppose that

$$\begin{array}{r}\alpha =\{\xi :f\left(v_i\right)+f\left(v_{i+1}\right)\equiv \xi \left(\text{mod}p\right),0<\xi <p,i=1,2,\dots ,p,i\ne (p-1)/2\}\end{array}$$

and

$$\begin{array}{r}\beta =\{\xi :f\left(v_1\right)+f\left(v_p\right)\equiv \xi \left(\text{mod}p\right),0<\xi <p\}.\end{array}$$

Thus, $\alpha \cup \beta =\{1,2,\dots ,p-1\}$. By Theorem 2.9, there are $\frac{p-1}{2}$ quadratic residues and $\frac{p-1}{2}$ quadratic nonresidues of $p$ in the set $\alpha \cup \beta .$ Additionally, notice that $f_p^{\ast }(v_{(p-1)/2}{v}_{(p+1)/2})=0$. Therefore, $e_{f_p^{\ast }}(0)=\frac{p-1}{2}+1$ and $e_{f_p^{\ast }}(1)=\frac{p-1}{2}.$ Hence, $|e_{f_p^{\ast }}(0)-e_{f_p^{\ast }}(1)|=1$ and it follows that $C_p$ admits a Legendre cordial labeling modulo $p$. □

Example 3.5. The Legendre cordial labeling modulo $p$ of the cycle graph $C_p$, with $p=7$, is shown in Fig. 2.

Fig. 2. Legendre cordial labeling modulo $7$ of $C_7$.

Theorem 3.6. The star graph $S_p$ is a Legendre cordial graph modulo $p$.

Proof. Let $V(S_p)=\{v_1,v_2,\dots ,v_p\}$ where $v_p$ is a central vertex. Now, let $f:V(S_p)\to \{1,2,\dots ,p\}$ be a bijective function defined by $f(v_i)=i$ for $i=1,2,\dots ,p$. So, for $v_i{v}_p\in E(S_p)$, $f(v_i)+f(v_p)\equiv i(\text{mod}p)$ for $i=1,2,\dots ,p-1.$ In view of this labeling, suppose that

$$\begin{array}{r}\alpha =\{\xi :f\left(v_i\right)+f\left(v_p\right)\equiv \xi \left(\text{mod}p\right),0<\xi <p,i=1,2,\dots ,p-1\}.\end{array}$$

Consequently, $\alpha =\{1,2,\dots ,p-1\}$. According to Theorem 2.9, there are $\frac{p-1}{2}$ quadratic residues and $\frac{p-1}{2}$ quadratic nonresidues of $p$ in set $\alpha .$ Therefore, $e_{f_p^{\ast }}(0)=e_{f_p^{\ast }}(1)=\frac{p-1}{2}$ and it follows that $|e_{f_p^{\ast }}(0)-e_{f_p^{\ast }}(1)|=0$. Hence, $S_p$ admits a Legendre cordial labeling modulo $p$. □

Example 3.7. An illustration of the Legendre cordial labeling modulo $p$ of the star graph $S_p$ for $p=7$ is provided in Fig. 3.

Fig. 3. Legendre cordial labeling modulo $7$ of $S_7$.

Theorem 3.8. The tadpole graph $T_{p,p}$ is a Legendre cordial graph modulo $p$.

Proof. According to Lemma 3.1, there exists an integer $k$, $0\le k<p$, such that $\left(\frac{p+2k+1}{2}/p\right)=1.$ Let $C_p$ be a cycle and $P_{p+1}$ be a path of $T_{p,p}$ with $V(C_p)=\{v_1,v_2,\dots ,v_p\}$ and $V(P_{p+1})=\{v_k,u_1,u_2,\dots ,u_p\}$. We define the bijective function $f:V(T_{p,p})\to \{1,2,\dots ,2p\}$ by $f(v_i)=i$ for $i=1,2,\dots ,p$, and

$$\begin{array}{r}f\left(u_i\right)=\{\begin{array}{l}i+{\displaystyle \frac{p-1}{2}}+p\text{ for }i=1,2,\dots ,{\displaystyle \frac{p+1}{2}}\\ i-{\displaystyle \frac{p+1}{2}}+p\text{ for }i={\displaystyle \frac{p+3}{2}},{\displaystyle \frac{p+5}{2}},\dots ,p.\end{array}\end{array}$$

For the edges of $C_p$,

$$\begin{array}{r}f\left(v_i\right)+f\left(v_{i+1}\right)\equiv \{\begin{array}{ll}(2i+1)\left(\text{mod}p\right)& \text{ for }i=1,2,\dots ,{\displaystyle \frac{p-3}{2}}\\ 0\left(\text{mod}p\right)& \text{ for }i={\displaystyle \frac{p-1}{2}}\\ (2i-p+1)\left(\text{mod}p\right)& \text{ for }i={\displaystyle \frac{p+1}{2}},{\displaystyle \frac{p+3}{2}},\dots ,p,\end{array}\end{array}$$

and $f(v_1)+f(v_p)\equiv 1(\text{mod}p).$ For the edges of $P_{p+1}$,

$$\begin{array}{r}f\left(u_i\right)+f\left(u_{i+1}\right)\equiv \{\begin{array}{ll}2i\left(\text{mod }p\right)& \text{ for }i=1,2,\dots ,{\displaystyle \frac{p-1}{2}}\\ (2i-p)\left(\text{mod}p\right)& \text{ for }i={\displaystyle \frac{p+1}{2}},{\displaystyle \frac{p+3}{2}},\dots ,p-1.\end{array}\end{array}$$

and $f(v_k)+f(u_1)\equiv \frac{p+2k+1}{2}(\text{mod}p).$

In view of the above labeling, let

$$\begin{array}{r}\alpha =\{\xi :f(v_i)+f(v_{i+1})\equiv \xi (\text{mod}p),0<\xi <p,i=1,2,\dots ,p,i\ne (p-1)/2\},\end{array}$$

$$\begin{array}{r}\beta =\{\xi :f(v_1)+f(v_p)\equiv \xi (\text{mod}p),0<\xi <p\},and\end{array}$$

$$\begin{array}{r}\gamma =\{\xi :f(u_i)+f(u_{i+1})\equiv \xi (\text{mod}p),0<\xi <p,i=1,2,\dots ,p-1\}.\end{array}$$

Thus, $\alpha \cup \beta =\gamma =\{1,2,\dots ,p-1\}.$ According to Theorem 2.9, there are $\frac{p-1}{2}$ quadratic residues and $\frac{p-1}{2}$ quadratic nonresidues of $p$ in the sets $\alpha \cup \beta$ and $\gamma$. Additionally, notice that $f_p^{\ast }(v_{(p-1)/2}{v}_{(p+1)/2})=0$ and $f_p^{\ast }(v_k{u}_1)=1$. Therefore, $e_{f_p^{\ast }}(0)=e_{f_p^{\ast }}(1)=2\left(\frac{p-1}{2}\right)+1=p$. Hence, $|e_{f_p^{\ast }}(0)-e_{f_p^{\ast }}(1)|=0$ and it follows that $T_{p,p}$ admits a Legendre cordial labeling modulo $p$. □

Example 3.9. In Fig. 4, one can observe the Legendre cordial labeling modulo $p$ of the tadpole graph $T_{p,p}$ for a particular case when $p=7$.

Fig. 4. Legendre cordial labeling modulo $7$ of $T_{7,7}$.

Theorem 3.10. The kayak paddle graph $K{P}_{p,p,p}$ is a Legendre cordial graph modulo $p$.

Proof. Note that there exist integers $k_1$ and $k_2$, $0\le k_1,k_2<p$, for which $\left({\displaystyle \frac{p+2k_1+1}{2}}/p\right)=\left({\displaystyle \frac{p+2k_2-1}{2}}/p\right)=1$ according to Lemma 3.1. Now, suppose that $C_p^1$ and $C_p^2$ are cycles of $K{P}_{p,p,p}$ with $V(C_p^j)=\{v_1^j,v_2^j,\dots ,v_p^j\}$ for $j=1,2$, and let $P_{p+2}$ be the path of $K{P}_{p,p,p}$ with $V(P_{p+2})=\{v_{k_1}^1,u_1,u_2,\dots ,u_p,v_{k_2}^2\}$. Furthermore, define the bijective function $f:V(K{P}_{p,p,p})\to \{1,2,\dots ,3p\}$ by $f(v_i^1)=i$ and $f(v_i^2)=i+2p$ for $i=1,2,\dots ,p$, and

$$\begin{array}{r}f\left(u_i\right)=\{\begin{array}{ll}i+{\displaystyle \frac{p-1}{2}}+p& \text{ for }i=1,2,\dots ,{\displaystyle \frac{p+1}{2}}\\ i-{\displaystyle \frac{p+1}{2}}+p& \text{ for }i={\displaystyle \frac{p+3}{2}},{\displaystyle \frac{p+5}{2}},\dots ,p.\end{array}\end{array}$$

For the edges of $C_p^j$,

$$\begin{array}{r}f\left(v_i^j\right)+f\left(v_{i+1}^j\right)\equiv \{\begin{array}{ll}(2i+1)\left(\text{mod}p\right)& \text{ for }i=1,2,\dots ,{\displaystyle \frac{p-3}{2}}\\ 0\left(\text{mod}p\right)& \text{ for }i={\displaystyle \frac{p-1}{2}}\\ (2i-p+1)\left(\text{mod}p\right)& \text{ for }i={\displaystyle \frac{p+1}{2}},{\displaystyle \frac{p+3}{2}},\dots ,p,\end{array}\end{array}$$

and $f(v_1^j)+f(v_p^j)\equiv 1(\text{mod}p)$ for $j=1,2$. For the edges of $P_{p+2}$,

$$\begin{array}{r}f\left(u_i\right)+f\left(u_{i+1}\right)\equiv \{\begin{array}{ll}2i\left(\text{mod}p\right)& \text{ for }i=1,2,\dots ,{\displaystyle \frac{p-1}{2}}\\ (2i-p)\left(\text{mod}p\right)& \text{ for }i={\displaystyle \frac{p+1}{2}},{\displaystyle \frac{p+3}{2}},\dots ,p-1,\end{array}\end{array}$$

$f(v_{k_1}^1)+f(u_1)\equiv {\displaystyle \frac{p+2k_1+1}{2}}(\text{mod}p)$, and $f(u_p)+f(v_{k_2}^2)\equiv {\displaystyle \frac{p+2k_2-1}{2}}(\text{mod}p)$.

In view of the above labeling, let

$$\begin{array}{r}{\alpha }_j=\{\xi :f(v_i^j)+f(v_{i+1}^j)\equiv \xi (\text{mod}p),0<\xi <p,i=1,2,\dots ,p,i\ne (p-1)/2\},and\end{array}$$

$$\begin{array}{r}{\beta }_j=\{\xi :f(v_1^j)+f(v_p^j)\equiv \xi (\text{mod}p),0<\xi <p\}\end{array}$$

for $j=1,2$, and suppose that

$$\begin{array}{r}\gamma =\{\xi :f\left(u_i\right)+f\left(u_{i+1}\right)\equiv \xi \left(\text{mod}p\right),0<\xi <p,i=1,2,\dots ,p-1\}.\end{array}$$

So, ${\alpha }_1\cup {\beta }_1={\alpha }_2\cup {\beta }_2=\gamma =\{1,2,\dots ,p-1\}.$ By Theorem 2.9, there are $\frac{p-1}{2}$ quadratic residues and $\frac{p-1}{2}$ quadratic nonresidues of $p$ in the sets ${\alpha }_1\cup {\beta }_1,$ ${\alpha }_2\cup {\beta }_2$, and $\gamma$. Additionally, observe that $f_p^{\ast }(v_{(p-1)/2}^j{v}_{(p+1)/2}^j)=0$ for $j=1,2$, and $f_p^{\ast }(v_{k_1}^1{u}_1)=f_p^{\ast }(u_p{v}_{k_2}^2)=1$. Thus, $e_{f_p^{\ast }}(0)=e_{f_p^{\ast }}(1)=3\left(\frac{p-1}{2}\right)+2$. Consequently, $|e_{f_p^{\ast }}(0)-e_{f_p^{\ast }}(1)|=0$ and it follows that $K{P}_{p,p,p}$ admits a Legendre cordial labeling modulo $p.$ □

Example 3.11. Fig. 5 shows the Legendre cordial labeling modulo $p$ of the kayak paddle graph $K{P}_{p,p,p}$ when $p=5$.

Fig. 5. Legendre cordial labeling modulo $5$ of $K{P}_{5,5,5}$.

Theorem 3.12. The bistar graph $B_{p,p}$ is a Legendre cordial graph modulo $p$.

Proof. Let $S_p^1$ and $S_p^2$ be star graphs of $B_{p,p}$ with $V(S_p^j)=\{v_1^j,v_2^j,\dots ,v_p^j\}$ where $v_p^j$ is the central vertex of $S_p^j$, for $j=1,2.$ Now, let $f:V(B_{p,p})\to \{1,2,\dots ,2p\}$ be a bijective function defined by $f(v_i^j)=i+(j-1)p$ for $i=1,2,\dots ,p$ and $j=1,2$. So, for $v_i^j{v}_p^j\in E\left(B_{p,p}\right)$, $f(v_i^j)+f(v_p^j)\equiv i(\text{mod}p)$ for $i=1,2,\dots ,p-1$ and $j=1,2$, and for $v_p^1{v}_p^2\in E(B_{p,p})$, $f(v_p^1)+f(v_p^2)\equiv 0(\text{mod}p)$. Given this labeling, let

$$\begin{array}{r}{\alpha }_j=\{\xi :f\left(v_i^j\right)+f\left(v_p^j\right)\equiv \xi \left(\text{mod}p\right),0<\xi <p,i=1,2,\dots ,p-1\}\end{array}$$

for $j=1,2$. Thus, ${\alpha }_1={\alpha }_2=\{1,2,\dots p-1\}$ and by Theorem 2.9, there are $\frac{p-1}{2}$ quadratic residues and $\frac{p-1}{2}$ quadratic nonresidues of $p$ in the sets ${\alpha }_1$ and ${\alpha }_2$. Additionally, observe that $f_p^{\ast }(v_p^1{v}_p^2)=0$. So, $e_{f_p^{\ast }}(0)=2\left(\frac{p-1}{2}\right)+1=p$ and $e_{f_p^{\ast }}(1)=2\left(\frac{p-1}{2}\right)=p-1$. Hence, $|e_{f_p^{\ast }}(0)-e_{f_p^{\ast }}(1)|=1$ and it follows that $B_{p,p}$ admits a Legendre cordial labeling modulo $p$. □

Example 3.13. Fig. 6 shows the Legendre cordial labeling modulo $p$ of the bistar graph $B_{p,p}$, where $p=7$.

Fig. 6. Legendre cordial labeling modulo $7$ of $B_{7,7}$.

Theorem 3.14. The fan graph $F_{p+1}$ is a Legendre cordial graph modulo $p$.

Proof. Let $P_p$ be a path of $F_{p+1}$ with $V(P_p)=\{v_1,v_2,\dots ,v_p\}$. Suppose that $v_{p+1}$ is a new vertex for which $v_i{v}_{p+1}\in E(F_{p+1})$ for $i=1,2,\dots ,p$. Now, let $f:V(F_{p+1})\to \{1,2,\dots ,p+1\}$ be a bijective function defined by

$$\begin{array}{r}f\left(v_i\right)=\{\begin{array}{ll}i+{\displaystyle \frac{p-1}{2}}& \text{ for }i=1,2,\dots ,{\displaystyle \frac{p+1}{2}}\\ i-{\displaystyle \frac{p+1}{2}}& \text{ for }i={\displaystyle \frac{p+3}{2}},{\displaystyle \frac{p+5}{2}},\dots ,p,\end{array}\end{array}$$

and $f(v_{p+1})=p+1.$ For the edges of $P_p,$

$$\begin{array}{r}f\left(v_i\right)+f\left(v_{i+1}\right)\equiv \{\begin{array}{ll}2i\left(\text{mod}p\right)& \text{ for }i=1,2,\dots ,{\displaystyle \frac{p-1}{2}}\\ (2i-p)\left(\text{mod}p\right)& \text{ for }i={\displaystyle \frac{p+1}{2}},{\displaystyle \frac{p+3}{2}},\dots ,p-1.\end{array}\end{array}$$

For the remaining the edges of $F_{p+1},$

$$\begin{array}{r}f\left(v_i\right)+f\left(v_{p+1}\right)\equiv \{\begin{array}{ll}(i+{\displaystyle \frac{p+1}{2}})\left(\text{mod}p\right)& \text{ for }i=1,2,\dots ,{\displaystyle \frac{p-3}{2}}\\ 0\left(\text{mod}p\right)& \text{ for }i={\displaystyle \frac{p-1}{2}}\\ (i-{\displaystyle \frac{p-1}{2}})\left(\text{mod}p\right)& \text{ for }i={\displaystyle \frac{p+1}{2}},{\displaystyle \frac{p+3}{2}},\dots ,p-1.\end{array}\end{array}$$

In view of the above labeling, let

$$\begin{array}{r}\alpha =\{\xi :f(v_i)+f(v_{i+1})\equiv \xi (\text{mod}p),0<\xi <p,i=1,2,\dots ,p-1\},and\end{array}$$

$$\begin{array}{r}\beta =\{\xi :f(v_i)+f(v_{p+1})\equiv \xi (\text{mod}p),0<\xi <p,i=1,2,\dots ,p,i\ne (p-1)/2\}.\end{array}$$

Thus, $\alpha =\beta =\{1,2,\dots ,p-1\}$ and by Theorem 2.9, there are $\frac{p-1}{2}$ quadratic residues and $\frac{p-1}{2}$ quadratic nonresidues of $p$ in sets $\alpha$ and $\beta$. Additionally, notice that $f_p^{\ast }(v_{(p-1)/2}{v}_{p+1})=0$. Hence, $e_{f_p^{\ast }}(0)=2\left(\frac{p-1}{2}\right)+1=p$ and $e_{f_p^{\ast }}(0)=2\left(\frac{p-1}{2}\right)=p-1$. Clearly, $|e_{f_p^{\ast }}(0)-e_{f_p^{\ast }}(1)|=1$. Therefore, $F_{p+1}$ admits a Legendre cordial labeling modulo $p$. □

Example 3.15. Fig. 7 shows the Legendre cordial labeling modulo $p$ of the fan graph $F_{p+1}$ for the case $p=11$.

Fig. 7. Legendre cordial labeling modulo $11$ of $F_{12}$.

Conclusion

In this study, we proposed a new type of cordial labeling, called Legendre cordial labeling, which incorporates the Legendre symbol into graph labeling. We demonstrated that the path graph $P_p$, cycle graph $C_p$, star $S_p$, tadpole graph $T_{p,p}$, kayak paddle graph $K{P}_{p,p,p}$, bistar graph $B_{p,p}$, and fan graph $F_{p+1}$ admit a Legendre cordial labeling modulo $p$, where $p$ is an odd prime. This contributes to the growing field of cordial labeling by linking graph theory with classical number-theoretic ideas. Future work may focus on identifying other graph classes that admit this labeling and investigating possible applications in cryptography, network analysis, and related areas.