A Fibonacci cordial labeling of a graph \(G\) is an injective function \(f: V(G) \rightarrow \{F_0, F_1, \dots,\\ F_n\}\), where \(F_i\) denotes the \(i^{\text{th}}\) Fibonacci number, such that the induced edge labeling \(f^*: E(G) \rightarrow \{0,1\}\), given by \(f^*(uv) = (f(u) + f(v))\) \((\bmod\ 2)\), satisfies the balance condition \(|e_f(0) – e_f(1)| \le 1\). Here, \(e_f(0)\) and \(e_f(1)\) represent the number of edges labeled 0 and 1, respectively. A graph that admits such a labeling is termed a Fibonacci cordial graph. In this paper, we investigate the existence and construction of Fibonacci cordial labelings for several families of graphs, including Generalized Petersen graphs, open and closed helm graphs, joint sum graphs, and circulant graphs of small order. New results and examples are presented, contributing to the growing body of knowledge on graph labelings inspired by numerical sequences.
The study of graph labeling has long captivated researchers within the field of graph theory. Among the many labeling concepts, a graph is said to be cordial if its vertices can be labeled with \(0\)s and \(1\)s such that the induced edge labels, based on the absolute difference of vertex labels, result in the number of vertices (or edges) labeled \(0\) and those labeled \(1\) differing by at most one. The concept of cordial labeling was introduced by Cahit in 1987 as a variation of graceful and harmonious labeling schemes [3]. Since then, numerous researchers have contributed to the study of various forms of cordial labelings. A comprehensive and periodically updated survey of graph labelings is maintained by Gallian [4].
Definition 1.1. A function \(f:V(G)\rightarrow \{0,1\}\) is said to be Cordial Labeling if the induced function \(f^*:E(G)\rightarrow \{0,1\}\) defined by \[f^*(uv)=\vert f(u)-f(v)\vert ,\] satisfies the conditions \(\vert n_0-n_1\vert \le 1\), as well as \(\vert \varepsilon_0-\varepsilon_1\vert \le 1\), where, \(n_i\) and \(\varepsilon_i\) denote the number of vertices and edges labeled \(i\), respectively, for \(i = 0,1\).
Over time, many variations of cordial labeling have been proposed. In 2013, Sridevi et al. [11] showed that paths and cycles are Fibonacci divisor cordial graphs. Building on the idea of cordiality, Rokad and Ghodasara introduced Fibonacci cordial labeling [10], where vertices are labeled with Fibonacci numbers rather than binary values.
Definition 1.2. The sequence \(F_n\) of Fibonacci numbers is defined by the recurrence relation: \[F_n = F_{n-1} + F_{n-2};\ \ F_0=0, F_1=F_2=1.\]
Definition 1.3. An injective function \(f:V(G)\rightarrow \{F_0,F_1,\cdots,F_n\}\) is said to be Fibonacci cordial labeling if the induced function \(f^*:E(G)\rightarrow \{0,1\}\) defined by \[f^*(uv)=(f(u)+f(v)) \ (\mod 2),\] satisfies the condition \(\vert \varepsilon_0-\varepsilon_1\vert \le 1\).
Rokad and Ghodasara provided Fibonacci cordiality results for several families of graphs, including the Petersen graph, wheel graphs, shell graphs, bistars, and certain product graphs such as coronas. Further investigations by Rokad in 2017 [9] expanded these results to additional graph families. In [6], we explored the Fibonacci cordiality of complete graphs, cycles, and corona products of the form \(C_n \odot K_m\) for \(m \leq 3\). This work was later extended to the generalized families \(C_n \odot K_m\) and \(C_n \odot \overline{K_m}\) in [1]. Recent contributions to this area can also be found in [8, 7, 5, 12].
In this paper, we investigate the Fibonacci cordiality of Generalized Petersen graphs, helm graphs, closed helm graphs, joint sum graphs, and finally, circulant graphs. Throughout, we denote \(\tilde{\varepsilon}:= \left| \varepsilon_1 – \varepsilon_0 \right|\), the absolute difference between the number of edges labeled \(1\) and those labeled \(0\).
Watkins introduced the generalized Petersen graph (abbreviated as GP) in [13]. For any integer \(n \ge 3\) and \(k \in \{1, 2, \ldots, \lfloor (n-1)/2 \rfloor\}\), the graph \(\mathrm{GP}(n,k)\) is defined with the vertex set \(V = \{ u_i, v_i : 1 \le i \le n \}\) and the edge set \(E = \{ u_i u_{i+k},\ u_i v_i,\ v_i v_{i+1} : 1 \le i \le n \}\), where the indices are taken modulo \(n\). According to this notation, \({\rm GP}(5,2)\) is the classic Petersen graph. In this paper we consider \({\rm GP}(n,1)\), and provide the Fibonacci cordial labeling for that family of graphs.
Theorem 2.1. The generalized Petersen graph \({\rm GP}(n,1)\) is Fibonacci cordial.
Proof. We prove the result by constructing a Fibonacci cordial labeling for \({\rm GP}(n,1)\), considering three cases based on the residue class of \(n\) modulo 3. Let \(f: V({\rm GP}(n,1))\rightarrow\{F_0, F_1, \cdots, F_{2n}\}\) be the labeling function defined differently in the three cases below.
Case 1. \(n=3p\)
For \(p \equiv k\ (\mod 4)\), we define,
\[p_1 = \begin{cases} (5p-k)/4, & \text{if } k=0,1,2,\\ (5p+1)/4, & \text{if } k=3. \end{cases} \qquad p_2 = \begin{cases} 2p+1-p_1, & \text{if } k=2,\\ 2p-p_1, & \text{if } k=0,1,3. \end{cases}\]
Define the vertex labeling \(f:V({\rm GP}(n,1))\rightarrow\{F_0, F_1, \cdots, F_{2n}\}\) as follows: \[f(u_i) = \begin{cases} \displaystyle F_{\lfloor (3i-1)/{2} \rfloor }, & \text{for }1\le i\le n-p_2,\\ \displaystyle F_{3(p_1+p_2+i-n)}, & \text{for } n+1-p_2\le i\le n-1,\\ \displaystyle F_{3(p_1+p_2)}, & \text{for } i=n \text{ and } k= 0,1,3, \\ \displaystyle F_{0}, & \text{for } i=n \text{ and } k=2 .\\ \end{cases}\]
For even \(i\) with \(2 \le i \le 2p_1\), set \(f(v_i) = F_{3i/2}\). For \(2p_1 + 1 \le i \le n\), define
\[f(v_i) = \begin{cases} F_{\lfloor (n+3i-1)/2\rfloor }, & \text{for } k= 0,1,3 , \\ F_{n+i-2-\lceil (n-i)/2\rceil}, & \text{for } k= 2 .\\ \end{cases}\]
Finally let \(f(u_{n-p_2})= F_{k}\), then for \(1\le i\le 2p_1-1\) when \(i\) is odd, \[f(v_i) = \begin{cases} F_{n+i+\ell- \lfloor i/4\rfloor }, & \text{if } k\equiv 1 \ (\mod 3) , \\ \displaystyle F_{n+i+\ell- \lceil \frac{n-i}{2} \rceil }, & \text{if } k\equiv 2 \ (\mod 3), \end{cases}\] where \[\ell = \begin{cases} \Big\lfloor \frac{3p}{8}\Big \rfloor, & \text{for } k= 0, 1,\\ \bigg\lfloor \frac{3(p-5)}{8}\bigg \rfloor, & \text{for } k=2,\\ \bigg\lfloor \frac{3(p+1)}{8}\bigg \rfloor, & \text{for } k=3. \end{cases}\]
If \(\ell < 0\), we redefine it as \(\ell := \ell + 1\); this adjustment is applied throughout the proof—including in the other cases—whenever necessary.
It is evident from the above construction that the labeling assigns even Fibonacci numbers to exactly \(p_1 + p_2\) vertices of \(G\). Observe that the vertices \(\{v_1, v_2, \ldots, v_{2p_1}\}\) are labeled alternately with odd and even Fibonacci labels (starting with odd). The remaining vertices \(\{v_{2p_1+1}, v_{2p_1+2}, \ldots, v_{n}\}\) all receive odd labels. Thus, on the outer circle, we obtain \(\varepsilon_0 = n-2p_1\), and \(\varepsilon_1 = 2p_1\).
On the other hand, on the inner circle \(\{u_1,u_2\cdots,u_{n-p_2}\}\) and \(\{u_{n-p_2+1},\cdots,u_{n}\}\) receive odd and even parity, respectively, and hence the above labeling contributes \(\varepsilon_0 = n – 2\), and \(\varepsilon_1 = 2\).
Among the spokes, exactly \((p_1 + p_2 – 2)\) have endpoints of different parity, contributing to \(\varepsilon_1\), while the remaining \((n – p_1 – p_2 + 2)\) contribute to \(\varepsilon_0\).
Combining all contributions, the total number of edges labeled with \(0\) and \(1\) are respectively \[\varepsilon_0 = 3n – 3p_1 – p_2, \quad \varepsilon_1 = 3p_1 + p_2.\]
Therefore, the difference is \[\tilde{\varepsilon} = |\varepsilon_0 – \varepsilon_1| = |6p_1 + 2p_2 – 3n|,\] which satisfies \(\tilde{\varepsilon} \leq 1\) for all \(p\), as can be easily verified. Hence, \(G\) is Fibonacci cordial in this case.
Case 2. \(n=3p+1\)
Assume \(p \equiv k\ (\mod 4)\). Define: \[p_1 = \begin{cases} \frac{5p – k}{4}, & \text{if } k = 0,1,\\ \frac{5p + 2}{4}, & \text{if } k = 2,\\ \frac{5p + 1}{4}, & \text{if } k = 3. \end{cases} \qquad p_2 = \begin{cases} 2p – p_1, & \text{if } k = 0,1,2,\\ 2p + 1 – p_1, & \text{if } k = 3. \end{cases}\]
We define the labeling \(f\) as follows:
\[f(u_i) = \begin{cases} \displaystyle F_{\lfloor (3i-1)/{2} \rfloor }, & \text{for }1\le i\le n-p_2,\\ \displaystyle F_{3(p_1+p_2+i-n)}, & \text{for } n+1-p_2\le i\le n-1,\\ \displaystyle F_{3(p_1+p_2)}, & \text{for } i=n \text{ and } k=0,1,2, \\ \displaystyle F_{0}, & \text{for } i=n \text{ and } k=3 ,\\ \end{cases}\] \(f(v_i)=F_{3i/2}\) for \(i\) even and \(2\le i\le 2p_1\). Now for \(2p_1+1\le i\le n\), \[f(v_i) = \begin{cases} F_{n+i-\lfloor (n-i)/2\rfloor }, & \text{for } k=0,1,2 ,\\ F_{n+i-1-\lceil (n-i)/2\rceil}, & \text{for } k=3 .\\ \end{cases}\]
Finally let \(f(u_{n-p_2})= F_{k}\), then for \(1\le i\le 2p_1-1\) when \(i\) is odd, \[f(v_i) = \begin{cases} F_{n+i+\ell- \lfloor i/4\rfloor }, & \text{if } k\equiv 2 \ (\mod 3), \\ \displaystyle F_{n+i+\ell- \lceil \frac{n-i}{2} \rceil }, & \text{if } k\equiv 1 \ (\mod 3) , \end{cases}\] where \[\ell = \begin{cases} \left\lfloor \frac{3(p + 2)}{8} \right\rfloor, & \text{if } k = 0,\\ \left\lfloor \frac{3(p + 1)}{8} \right\rfloor, & \text{if } k = 1, \left\lfloor \frac{3(p + 4)}{8} \right\rfloor, & \text{if } k = 2,\\ \left\lfloor \frac{3(p – 1)}{8} \right\rfloor, & \text{if } k = 3. \end{cases}\]
The reader can verify the parity distribution to confirm that the edge labels are indeed balanced, as asserted.
Case 3. \(n = 3p + 2\)
Assume \(p \equiv k\ (\mod 4)\). Define: \[p_1 = \begin{cases} \frac{5p}{4} + 1, & \text{if } k = 0,\\ \frac{5p + 3}{4}, & \text{if } k = 1,\\ \frac{5p + 2}{4}, & \text{if } k = 2,\\ \frac{5p}{4}, & \text{if } k = 3. \end{cases} \qquad p_2 = \begin{cases} 2p + 1 – p_1, & \text{if } k = 0,1,3,\\ 2p + 2 – p_1, & \text{if } k = 2. \end{cases}\]
We define the labeling \(f\) as follows:
\[f(u_i) = \begin{cases} \displaystyle F_{\lfloor (3i-1)/{2} \rfloor }, & \text{for }1\le i\le n-p_2,\\ \displaystyle F_{3(p_1+p_2+i-n)}, & \text{for } n+1-p_2\le i\le n-1,\\ \displaystyle F_{3(p_1+p_2)}, & \text{for } i=n \text{ and } k=0,1,2, \\ \displaystyle F_{0}, & \text{for } i=n \text{ and } k=3 .\\ \end{cases}\]
\(f(v_i)=F_{3i/2}\) for \(i\) even and \(2\le i\le 2p_1\). Now for \(2p_1+1\le i\le n\), \[f(v_i) = \begin{cases} F_{n+i-\lceil (n-i)/2\rceil}, & \text{for } k=0,1,3, \\ F_{n+i-2-\lfloor (n-i)/2\rfloor}, & \text{for } k=2. \\ \end{cases}\]
Finally let \(f(u_{n-p_2})= F_{k}\), then for \(1\le i\le 2p_1-1\) when \(i\) is odd, \[f(v_i) = \begin{cases} F_{n+i+\ell- \lfloor i/4\rfloor }, & \text{if } k\equiv 1 \ (\mod 3) ,\\ \displaystyle F_{n+i+\ell- \lceil \frac{n-i}{2} \rceil }, & \text{if } k\equiv 2 \ (\mod 3) , \end{cases}\] where \[\ell = \begin{cases} \left\lfloor \frac{3(p + 3)}{8} \right\rfloor, & \text{if } k = 0,\\ \left\lfloor \frac{3(p + 2)}{8} \right\rfloor, & \text{if } k = 1,\\ \left\lfloor \frac{3(p – 3)}{8} \right\rfloor, & \text{if } k = 2,\\ \left\lfloor \frac{3(p + 4)}{8} \right\rfloor, & \text{if } k = 3. \end{cases}\]
Once again, verifying the parity distribution confirms that the edge labels are balanced, thereby completing the proof. ◻
Next, we turn our attention to the helm graph \(H_n\), denoted by the graph obtained from an \(n-\)wheel graph by adjoining a pendant edge at each node of the cycle. We identify the vertices of \(H_n\) as \(V(H_n) =\{v\}\cup \{v_1,v_2,\cdots,v_n\}\cup \{u_1,u_2,\cdots,u_n\}\) where \(v_i\)’s are the vertices of cycle taken in clockwise and \(u_i\)’s are pendant vertices such that each \(v_iu_i\) is a pendant edge and \(v\) is the apex vertex of the cycle. Note that \(\vert V(H_n)\vert =2n+1\).
Theorem 2.2. Helm graphs \(H_n\) are Fibonacci cordial for \(n\ge 3\).
Proof. Let \(G\) be the graph \(H_n\). We identify \(n=4, 8\), and \(16\) as special cases and provide the individual Fibonacci labeling later. For the rest of the values of \(n\), first we determine the values of three parameters \(p_i\), \(i=1,2,3\). First, we have provided the value for \(p_3\) as follows, \[p_3 = \begin{cases} 0, & \text{if } n \equiv 0 \ (\mod 4),\\ 1, & \text{otherwise }. \end{cases}\]
Now we calculuate the values of \(p_1\) and \(p_2\) based on three congruence classes of \(n\). The following three cases are considered due to the fact that the number of available even Fibonacci numbers depends on the remainder of \(n\) when divided by \(3\).
Case 1. \(n=3p\).
We have \(p_1=\lfloor \frac{p-1}{4}\rfloor\), \(p_2=2p-p_1\).
Case 2. \(n=3p+1\), \(p\ge 2\).
In this case, if \(p \equiv 1 \ (\mod 4)\) then \(p_1=(p-9)/4\), otherwise \(p_1=\big\lfloor \frac{p-1}{4}\big\rfloor\). Finally we have \(p_2=2p+2-p_1-p_3\).
Case 3. \(n=3p+2\).
In this case we have \(p_2=2p+2-p_1-p_3\), where \[p_1 = \begin{cases} 1, & \text{for } p = 2,\\ \frac{p-6}{4}, & \text{for } p \equiv 2 \ (\mod 4)\text{ and } p>2,\\ \big\lfloor \frac{p+1}{4}\big \rfloor , & \text{otherwise }. \end{cases}\]
Now the vertex labeling of \(f: V (H_n)\rightarrow\{F_0,F_1,\cdots, F_{2n+1}\}\) is defined as follows:
\[f(v_i) = \begin{cases} F_{3(i-1)}, & \text{for } 1\le i< p_2 ,\\ F_{(i+n-p_2)+\lceil (i+n-p_2-5)/2\rceil}, & \text{for } p_2 \le i\le n-2p_1. \end{cases}\]
For \(n+1-2p_1\le i\le n-1\) \[f(v_i) = \begin{cases} F_{3(p_2+\lceil (i+2p_1-n)/2\rceil )}, & \text{if } n-i\equiv 1 (\mod 2) \text{\ and } p_3=1, \\ F_{3(p_2-1+\lceil (i+2p_1-n)/2\rceil)}, & \text{if } n-i\equiv 1 (\mod 2) \text{\ and } p_3=0,\\ F_{(3n+i)/2-p_1-p_2+\lceil (3n+i-2p_1-2p_2-10)/4\rceil )}, & \text{if } n-i\equiv 0 (\mod 2). \end{cases}\]
\[f(u_i) = \begin{cases} F_{3p_2}, & \text{for } i=1 \text{ \ and } p_3=1 ,\\ F_{3n-p_1-p_2-1+\lceil (-p_1-p_2)/2\rceil}, & \text{for } i=1 \text{ \ and } p_3 =0,\\ F_{i+\lceil (i-5)/2\rceil}, & \text{for } 2\le i\le n . \end{cases}\]
\[f(v) = \begin{cases} F_{3n+1-p_1-p_2+\lceil (-p_1-p_2-1)/2\rceil}, & \text{if } p_3 =0,\\ F_{3n-p_1-p_2-1+\lceil (-p_1-p_2)/2\rceil}, & \text{if } p_3 =1 . \end{cases}\]
Based on the labeling specified above, the center (hub) vertex receives an odd Fibonacci label. Without loss of generality, let us assume \(p_3=1\). Now for any value of \(n\), we have the labels on the inner cycle as follows, \(\{v_1,v_2,\ldots,v_{p_2-1}\}\) receive even and \(\{v_{p_2},v_{p_2+2},\ldots,v_{\,n-2p_1}\}\) receive odd Fibonacci labels. The remaining vertices \(\{v_{\,n-2p_1+1},\\v_{\,n-2p_1+2},\ldots,v_n\}\) are labeled alternately with even and odd Fibonacci numbers in alternating parity (starting with even). Among the pendant vertices, only one, namely \(u_1\), receives an even Fibonacci label, while every other vertex \(u_i\) (\(i\ge2\)) receives an odd Fibonacci label.
From this labeling assignment, we obtain \(p_1+(n-2p_1-p_2+1)\) many spoke edges, \((p_2-1)+(n-2p_1-p_2-1)\) many edges from the cycle, and \((n-2p_1-p_2+1)+p_1+1\) many pendant edges with the same parity on both ends. Hence, we get \(\varepsilon_0=3n-4p_1-2p_2+1\). Similarly, we obtain \(\varepsilon_1=4p_1+2p_2-1\). Thus \[\tilde{\varepsilon} = \vert \varepsilon_0 – \varepsilon_1 \vert = \vert 3n -8p_1 -4p_2 +2 \vert .\]
It can be easily checked that \(H_n\) is Fibonacci cordial under the above labeling for any value of \(n\) (\(n\ne 4,8,16\)).
Finally, we provide Fibonacci cordial labeling of the special cases (\(n=4,8,16\)). Fibonacci cordial labeling for \(H_4\) is provided in Figure 2.
For \(n=8,16\), we follow the following pattern: \(f(u_i)=i+\lceil (i-2)/2\rceil\) for \(1\le i\le n\) and \[f(v_i) = \begin{cases} F_{3(i-1)}, & \text{for } 1\le i\le p_2,\\ F_{i+n-p_2-1+\lceil (i+n-p_2)/2\rceil}, & \text{for } p_2+1 \le i\le n, \\ F_{17}, & \text{if } n=8 ,\\ F_{32}, & \text{if } n=16 . \\ \end{cases}\] ◻
A closed helm \({\rm CH}_n\) (see Figure 3) is the graph obtained by taking a helm \(H_n\) and adding edges between the outer pendant vertices, i.e., completing the outer circle.
Theorem 2.3. Closed Helm graphs \({\rm CH}_n\) are Fibonacci cordial for all \(n\ge 3\).
Proof. Let \(G\) be the graph \({\rm CH}_n\). Due to the same reason as mentioned before, we consider three cases based on the value of \(n\). Note that \(|V({\rm CH}_n)| = 2n + 1\) and \(|E({\rm CH}_n)| = 4n\), which is even. Therefore, any Fibonacci cordial labeling of \({\rm CH}_n\) must satisfy \(\varepsilon_0 = \varepsilon_1\). The vertex labeling of \(f: V ({\rm CH}_n)\rightarrow\{F_0,F_1,\cdots, F_{2n+1}\}\) is defined as follows:
Case 1. \(n=3p\). \[f(u_i) = \begin{cases} F_{3i/2}, & \text{for } 1\le i\le 2p_1 \text{ and } i \equiv 0 \ (\mod 2),\\ F_{\lfloor (3i+1)/4\rfloor}, & \text{for } 1\le i\le 2p_1 \text{ and } i \equiv 1 \ (\mod 2),\\ F_{\lceil 3(i-p_1)/2-1 \rceil}, & \text{for } 2p_1+1\le i\le n. \end{cases}\] \[f(v_i) = \begin{cases} F_{3(2p_1+i+1)/2}, & \text{for } 1\le i\le 2p_2 \text{ and } i \equiv 1 \ (\mod 2),\\ F_{\lceil 3(i/2+n-p_1)/2\rceil-1}, & \text{for } 1\le i\le 2p_2 \text{ and } i \equiv 0 \ (\mod 2),\\ \displaystyle F_{n+i+p_3 + \lfloor (i+p_3+1-n)/2 \rfloor-1}, & \text{for } 2p_2+1\le i\le n-p_3,\\ \displaystyle F_{[2n- 3(n-i)]}, & \text{for } n-p_3+1\le i\le n, \end{cases}\] where \(p_2=p_3=\lceil p/2 \rceil\) and \(p_1=2(p-\lceil p/2 \rceil)\), and finally \(f(v)=F_{2n+1}\).
Note that in the outer and inner circles, exactly \(p_1\) and \(p_2+p_3\) even Fibonacci labels have been used, respectively. On the outer circle, the vertices \(\{u_1, u_2, \ldots, u_{2p_1}\}\) are labeled alternately with odd and even Fibonacci labels (starting with odd), while the remaining vertices \(\{u_{2p_1+1}, u_{2p_1+2}, \ldots, u_{n}\}\) all receive odd labels. Hence, from the outer circle we obtain \(\varepsilon_0 = n – 2p_1\), and \(\varepsilon_1 = 2p_1\).
On the inner circle, the vertices \(\{v_1, v_2, \ldots, v_{2p_2}\}\) are labeled alternately with odd and even Fibonacci labels (starting with even). The next set of vertices \(\{v_{2p_2+1}, v_{2p_2+2}, \ldots, v_{n-p_3}\}\) are labeled with odd Fibonacci numbers, while the remaining \(\{v_{n-p_3+1}, v_{n-p_3+2}, \ldots, v_{n}\}\) are labeled with even Fibonacci numbers. Thus, the contribution from the inner circle is \(\varepsilon_0 = p_3 + (n – p_3 – 2p_2) = n – 2p_2\), and \(\varepsilon_1 = 2p_2\).
Since the hub vertex receives an odd label, the spokes (edges connecting the hub to the inner circle) contribute \(\varepsilon_0 = p_2 + (n – p_3 – 2p_2) = n – p_2 – p_3\), and \(\varepsilon_1 = p_2 + p_3\).
Finally, among the edges joining the inner and outer circles, exactly \((p_1 + p_2 + p_3)\) have different parities at their endpoints, contributing to \(\varepsilon_1\), while the remaining \((p_1 p_2 p_3)\) contribute to \(\varepsilon_0\).
Combining all contributions, we obtain \[\varepsilon_0 = 4n – 3p_1 – 4p_2 – 2p_3, \quad \varepsilon_1 = 3p_1 + 4p_2 + 2p_3.\]
Since \(p_1 + p_2 + p_3 = 2p\), it follows that \[\tilde{\varepsilon} = \vert \varepsilon_0 – \varepsilon_1 \vert = \vert 6p_1 + 8p_2 + 4p_3 – 4n \vert = \vert 2p_1 + 4p_2 – 4p \vert = 0.\]
Therefore, \({\rm CH}_n\) is Fibonacci cordial under the above labeling. Next, we provide the labeling for the rest of the cases for \(n\), but we skip the proof as those are very similar to the present one.
Case 2. \(n=3p+1\).
\[f(u_i) = \begin{cases} F_{3i/2}, & \text{for } 1\le i\le 2p_1 \text{ and } i \equiv 0 \ (\mod 2),\\ F_{\lfloor (3i+1)/4\rfloor}, & \text{for } 1\le i\le 2p_1 \text{ and } i \equiv 1 \ (\mod 2),\\ F_{\lceil 3(i-p_1)/2-1 \rceil}, & \text{for } 2p_1+1\le i\le n. \end{cases}\] \[f(v_i) = \begin{cases} F_{3(2p_1+i+1)/2}, & \text{for } 1\le i\le 2p_2 \text{ and } i \equiv 1 \ (\mod 2),\\ F_{\lceil 3(i/2+n-p_1)/2\rceil-1}, & \text{for } 1\le i\le 2p_2 \text{ and } i \equiv 0 \ (\mod 2),\\ \displaystyle F_{n+i+p_3 + \lfloor (i+p_3-n)/2 \rfloor-1}, & \text{for } 2p_2+1\le i\le n-p_3,\\ \displaystyle F_{2n+1- 3(n-i)}, & \text{for } n-p_3+1\le i\le n, \end{cases}\] where \(p_2=\lfloor p/2 \rfloor\), \(p_3=p_2+1\), \(p_1=2p+1-p_2-p_3\), and finally \(f(v)=F_{2n}\).
Case 3. \(n=3p+2\).
\[f(u_i) = \begin{cases} F_{3i/2}, & \text{for } 1\le i\le 2p_1 \text{ and } i \equiv 0 \ (\mod 2),\\ F_{\lfloor (3i+1)/4\rfloor}, & \text{for } 1\le i\le 2p_1 \text{ and } i \equiv 1 \ (\mod 2),\\ F_{\lceil 3(i-p_1)/2-1 \rceil}, & \text{for } 2p_1+1\le i\le n. \end{cases}\] \[f(v_i) = \begin{cases} F_{3(2p_1+i+1)/2}, & \text{for } 1\le i\le 2p_2 \text{ and } i \equiv 1 \ (\mod 2),\\ F_{\lceil 3(i/2+n-p_1)/2\rceil-1}, & \text{for } 1\le i\le 2p_2 \text{ and } i \equiv 0 \ (\mod 2),\\ \displaystyle F_{n+i+p_3 + \lfloor (i+p_3+1-n)/2 \rfloor-1}, & \text{for } 2p_2+1\le i\le n-p_3,\\ \displaystyle F_{2n-1- 3(n-i-2)}, & \text{for } n-p_3+1\le i\le n-1,\\ \displaystyle F_{0}, & \text{for } i=n, \end{cases}\] where \(p_2 = \lfloor p/2 \rfloor\), \(p_3=p_2+2\), \(p_1=2(p-p_2)\), and finally \(f(v)=F_{2n}\). ◻
Next, we introduce the concept of the joint sum of two graphs, as given below.
Definition 2.4. Joint sum \(G_1 \boxplus G_2\) of two graphs \(G_1\) and \(G_2\) is the graph obtained by connecting a vertex of \(G_1\) with a vertex of \(G_2\).
Theorem 2.5. \(F_m \boxplus P_n\) is Fibonacci cordial.
Proof. Let \(\{u,u_1,u_2,\cdots,u_m\}\) and \(\{v_1,v_2,\cdots,v_n\}\) be the vertices of \(F_m\) and \(P_n\) (\(u\) being the apex vertex of \(F_n\)). We obtain the graph \(F_m \boxplus P_n\) by connecting \(u\) and \(v_1\). We define \(f:V(F_m \boxplus P_n) \rightarrow \{F_0,F_1,\cdots, F_{m+n+1}\}\) as follows: \(f(u)=F_0\) and
\[f(u_j) = \begin{cases} \displaystyle F_{j+\lceil \frac{j-2}{2}\rceil }, & \text{for } 1\le j\le p_1+1,\\ \displaystyle F_{3(j-p_1)/2}, & \text{for } p_1+2 \le j\le p_1+2p_2 \text{\ and $j$ is of the same parity as $p_1$ },\\ \displaystyle F_{3(j-p_2-p_1)}, & \text{for } p_1+2p_2+1\le j\le m,\\ \displaystyle F_{\lfloor \frac{3(j+p_1+3)}{2}\rfloor -2}, & \text{for } p_1+3 \le j\le p_1+2p_2-1 \text{\ and $j$ is of the opposite parity as $p_1$}, \end{cases}\] where we obtain the values of \(p_1\) and \(p_2\) from below cases.
Case 1. \(m=6p\).
\(p_1=3p\), \(p_2=p\), and \(f(v_j) = \begin{cases} \displaystyle F_{j+n+1}, & \text{for } j\equiv 6,9,10 \ (\mod 12),\\ \displaystyle F_{j+n-1}, & \text{for } j\equiv 7 \ (\mod 12),\\ \displaystyle F_{j+n-2}, & \text{for } j\equiv 11 \ (\mod 12),\\ \displaystyle F_{j+n}, & \text{otherwise } . \end{cases}\)
Case 2. \(m=6p+1\).
\(p_1=3p+1\), \(p_2=p\), and \(f(v_j) = \begin{cases} \displaystyle F_{j+n+1}, & \text{for } j\equiv 2,4,7 \ (\mod 12),\\ \displaystyle F_{j+n-1}, & \text{for } j\equiv 3,5,8 \ (\mod 12),\\ \displaystyle F_{j+n}, & \text{otherwise } . \end{cases}\)
Case 3.] \(m=6p+2\).
\(p_1=3p+2\), \(p_2=p\), and \(f(v_j) = \begin{cases} \displaystyle F_{j+n-2}, & \text{for } j\equiv 3 \ (\mod 12),\\ \displaystyle F_{j+n-1}, & \text{for } j\equiv 11 \ (\mod 12),\\ \displaystyle F_{j+n+1}, & \text{for } j\equiv 1,2,10 \ (\mod 12),\\ \displaystyle F_{j+n}, & \text{otherwise } . \end{cases}\)
Case 4. \(m=6p+3\).
\(p_1=3p+3\), \(p_2=p\), and \(f(v_j) = \begin{cases} \displaystyle F_{j+n-2}, & \text{for } j\equiv 2,11 \ (\mod 12),\\ \displaystyle F_{j+n-1}, & \text{for } j\equiv 7 \ (\mod 12),\\ \displaystyle F_{j+n}, & \text{for } j\equiv 3,4,5,8 \ (\mod 12),\\ \displaystyle F_{j+n+1}, & \text{otherwise } . \end{cases}\)
Case 5. \(m=6p+4\).
\(p_1=3p+2\), \(p_2=p+1\), and \(f(v_j) = \begin{cases} \displaystyle F_{j+n-1}, & \text{for } j\equiv 0,3,10 \ (\mod 12),\\ \displaystyle F_{j+n+1}, & \text{for } j\equiv 1,4,11 \ (\mod 12),\\ \displaystyle F_{j+n}, & \text{otherwise } . \end{cases}\)
Case 6. \(m=6p+5\).
\(p_1=3p+2\), \(p_2=p+1\), and \(f(v_j) = \begin{cases} \displaystyle F_{j+n+1}, & \text{for } j\equiv 0,3,10 \ (\mod 12),\\ \displaystyle F_{j+n-1}, & \text{for } j\equiv 1,4,11 \ (\mod 12),\\ \displaystyle F_{j+n}, & \text{otherwise } . \end{cases}\)
Note that in the Fan component \(\{u_1,u_2, \cdots,u_{p_1+1}\}\) and \(\{u_{p_1+2p_2+1},\cdots, u_{m}\}\) are assigned odd and even Fibonacci labels, respectively, while the intermediate set \((\{u_{p_1+2},\cdots, u_{p_1+2p_2}\})\) receives alternating odd and even labels, beginning with an even label.
For the first case when when \(m=6p\), this labeling yields \(m-2p_2+1=6p-2p+1=4p+1\) edges of the cycle \(C_{m+1}\) whose endpoints share the same parity, and exactly \(2p\) edges of different parity. Furthermore, among the spoke edges, we obtain \(p_2+m-(p_1+2p_2+1)=2p-1\) edges of the same parity, and \(4p-1\) edges of different parity. Therefore, combining the contributions, we have \(\varepsilon_0=4p+1+2p-1=6p\), and similarly \(\varepsilon_1=6p-1\). It is important to note that the explicit labeling of the path \(P_{n+1}\) balances this discrepancy. The remaining cases can be established by analogous computations. ◻
Finally, we turn our attention to circulant graphs, a distinguished class of Cayley graphs renowned for their rich symmetry and enduring appeal among mathematicians. Circulant networks naturally generalize double loop networks, first introduced by Wong and Coppersmith [14]. For decades, circulant graphs have played a significant role in the design of computer and telecommunication networks, valued for their optimal fault-tolerance and efficient routing properties [2].
Definition 2.6. Let \(\mathbb{Z}_n\) be a cyclic group and \(S\subset \mathbb{Z}_n\) such that \(\{0\}\notin S\). Define a graph \(\Gamma = \Gamma(n,S)\) by \(V(\Gamma) = \mathbb{Z}_n\) and \(E(\Gamma) =\{(u,v): v-u\in S\}\). Such a graph is a circulant graph of order \(n\) with connection set \(S\). Note that \(S = S^{-1} = \{-s:s\in S\}\) for circulant graphs.
We focus our work mainly on “small” connection sets. Note that \(\vert S \vert \le n-1\), since \(\{0\}\notin S\) (no loops). Also when \(\vert S \vert = n-1\), then \(\Gamma\) becomes complete graph, and it is well known that \(\Gamma(n,\{1,2,\cdots,n-1\})\) is not Fibonacci cordial, except \(n=4,6,7,9,11,18,22\) (see [6]). Let us denote \(\tilde{\varepsilon}_f=\vert \varepsilon_f(0)-\varepsilon_f(1)\vert\) and \(\tilde{\varepsilon}_g=\vert \varepsilon_g(0)-\varepsilon_g(1)\vert\). We begin this section with the following result.
Theorem 2.7. For any two injective Fibonacci labelings \(f\) and \(g\) on the circulant graph \(\Gamma(n,\pm\{1, \\2, \ldots, j\})\), we have \(\tilde{\varepsilon}_f -\tilde{\varepsilon}_g \equiv 0 \pmod{4}\).
Proof. Without loss of generality, assume that the labelings \(f\) and \(g\) differ only at a single vertex \(v_0 \in V(\Gamma(n,\pm\{1, 2, \ldots, j\}))\), i.e., \(f(v_0) \neq g(v_0)\) and \(f(v) = g(v)\) for all \(v \neq v_0\). Let \(v_1, v_2, \ldots, v_{2j}\) denote the \(2j\) neighbors of \(v_0\) in the circulant graph. For the labeling \(f\), suppose that \(v_0\) shares the same parity with exactly \(k\) of its neighbors. Since \(f\) is a Fibonacci labeling, this means that \(k\) edges will have induced \(0\) labels, and the remaining \(2j-k\) edges have label \(1\). Thus, the contribution to \(\tilde{\varepsilon}_f\) from the edges incident to \(v_0\) is: \[\sum_{i=1}^{2j} f^*(v_0v_i) = \vert k – (2j – k) \vert = \vert 2k – 2j\vert .\]
Similarly, since \(f\) and \(g\) differ only at \(v_0\), the parity relations at \(v_0\) flip, and under \(g\), \(v_0\) has the same parity as \(2j – k\) neighbors. Therefore, \[\sum_{i=1}^{2j} g^*(v_0v_i) = \vert (2j – k)- k \vert =\vert 2j – 2k\vert .\] Then the net difference in total signed edge weights becomes: \[\tilde{\varepsilon}_f – \tilde{\varepsilon}_g =\vert 2k – 2j \vert – \vert 2j – 2k \vert \equiv 0 \pmod{4}.\]
Hence, the result follows. ◻
Corollary 2.8. For any injective function \(f:\Gamma\rightarrow\{F_0,F_1,\cdots,F_{n}\}\) on circulant graph \(\Gamma(n,\pm\{1, 2,\cdots,j\})\), if \(\vert \bar\varepsilon_f\vert = 2\pmod 4\), then \(\Gamma\) can not be converted FC.
Theorem 2.9. The circulant graph \(\Gamma(n,\pm\{1,2,\ldots,4m+1\})\), where \(m \le \frac{n-2}{4}\), is not Fibonacci cordial whenever \(n \equiv 2 \pmod{4}\).
Proof. Suppose \(n = 4q + 2\) for some positive integer \(q\). Then the number of edges in \(\Gamma\) is given by \[|E(\Gamma)| = (4q + 2)(4m + 1) = 4(4mq + 2m + q) + 2.\]
It follows that \(|E(\Gamma)| \equiv 2 \pmod{4}\). By the necessary condition established in the Corollary 2.8, this congruence implies that a Fibonacci cordial labeling is not possible. Hence, the result follows. ◻
Similar reasoning yields the following result.
Theorem 2.10. The circulant graph \(\Gamma(n,\pm\{1,2,\ldots,j\})\) is not Fibonacci cordial in the following cases:
(i) When \(j \equiv 2 \pmod{4}\) and \(n \equiv 1 \pmod{2}\),
(ii) When \(j \equiv 3 \pmod{4}\) and \(n \equiv 2 \pmod{4}\).
Theorem 2.11. The circulant graph \(\Gamma(n,\pm\{1,2\})\) is Fibonacci cordial if and only if \(n \not \equiv 1\ (\mod 2)\).
Proof. We need only to prove that \(\Gamma(n,\pm\{1,2\})\) is Fibonacci cordial when \(n\) is even, i.e., \(n \equiv 0 \pmod{2}\). We do so by explicitly constructing a Fibonacci cordial labeling of the vertices of \(\Gamma\). For \(n\equiv 2 \ (\mod 6)\) we consider the following function that assign even Fibonacci numbers to the vertices.
First, consider the case when \(n \equiv 2 \pmod{6}\). Define a vertex labeling function \(f\) as follows: \[f(v_i) = \begin{cases} F_0, & \text{if } i = 1, \\ F_3, & \text{if } i = 2, \\ F_{3i/2}, & \text{if } i \equiv 0 \pmod{4}, \\ F_{3(i+1)/2}, & \text{if } i \equiv 1 \pmod{4} \text{ and } i > 1, \end{cases}\] for \(i \leq \frac{2(n-2)}{3}\). The remaining vertices are labeled arbitrarily with distinct odd Fibonacci numbers to ensure balance in the edge label distribution.
For other even values of \(n\), we extend this labeling scheme:
\(\bullet\) If \(n \equiv 4 \pmod{6}\), define \(f\left(\frac{2n – 5}{3}\right) = F_{n-1}\).
\(\bullet\) If \(n \equiv 0 \pmod{6}\), define \(f\left(\frac{2n}{3}\right) = F_n\).
These assignments preserve the necessary distribution of edge labels as derived from Fibonacci values, thereby fulfilling the conditions for a Fibonacci cordial labeling and completing the proof. ◻
Theorem 2.12. The circulant graph \(\Gamma(n,\pm\{1,2,3\})\) is Fibonacci cordial if and only if \(n = 6\) or \(n \equiv 0,1,3 \pmod{4}\).
Proof. First, observe that when \(n = 6\), the circulant graph \(\Gamma(6,\pm\{1,2,3\})\) is isomorphic to the complete graph \(K_6\), which is known to be Fibonacci cordial (see [6]). Moreover, computational verification shows that \(\Gamma(n,\pm\{1,2,3\})\) is Fibonacci cordial for all \(7 \leq n \leq 28\); in particular, \(\Gamma(7,\pm\{1,2,3\})\) is also a complete graph and thus Fibonacci cordial.
It remains to construct a Fibonacci cordial labeling for \(n \geq 29\) when \(n \equiv 0,1,3 \pmod{4}\). We begin with an explicit construction for \(n \equiv 1 \pmod{12}\) and then describe how to extend or adapt this labeling to other congruence classes.
Note that we only detail the labeling of a subset of the vertices using even Fibonacci numbers. The remaining vertices can be assigned unused odd Fibonacci numbers in such a way that the edge labels are balanced, ensuring a Fibonacci cordial labeling.
Case 1.\(n \equiv 1 \pmod{12}\): For \(1 \leq i < 21\), define: \[f(v_i) = \begin{cases} F_{3i/2}, & \text{if } i = 2, 6, 10, 14, \\ F_{3(i-1)/2}, & \text{if } i = 1, 5, 9, 13, 17. \end{cases}\]
For \(21 \leq i < \frac{3(n-1)}{4}\), set: \[f(v_i) = \begin{cases} F_{(4i-3)/3}, & \text{if } i \equiv 3 \pmod{9}, \\ F_{(4i+2)/3}, & \text{if } i \equiv 4 \pmod{9}, \\ F_{(4i-1)/3}, & \text{if } i \equiv 7 \pmod{9}, \\ F_{(4i+5)/3}, & \text{if } i \equiv 8 \pmod{9}. \end{cases}\]
Case 2. \(n \equiv 3 \pmod{12}\): Extend the labeling from Case 1 and define \[f(v_{\frac{3(n-3)}{4}}) = F_{n}\]
Case 3. \(n \equiv 4 \pmod{12}\): Use the labeling from Case 1 and set \[f(v_{\frac{3n – 4}{4}}) = F_{n-1}.\]
Case 4. \(n \equiv 5 \pmod{12}\): Use the same labeling as in Case 1 for \(21 \leq i \leq \frac{3(n-1)}{4}\).
Case 5. \(n \equiv 7 \pmod{12}\): Use the same labeling as in Case 1 for \(21 \leq i < \frac{3(n-7)}{4}\), and then define: \[f(v_{\frac{3(n-7)}{4}}) = F_{n-4}, \quad f(v_{\frac{3n – 5}{4}}) = F_{n-1}.\]
Case 6. ] \(n \equiv 8 \pmod{12}\): Use the same labeling as in Case 1 for \(21 \leq i \leq \frac{3n – 8}{4}\).
Case 7. \(n \equiv 9 \pmod{12}\): Use the labeling from Case 8 and define \[f(v_{\frac{3n – 7}{4}}) = F_n.\]
Case 8. \(n \equiv 11 \pmod{12}\): Use the same labeling as in Case 1 for \(21 \leq i \leq \frac{3n – 5}{4}\).
Case 9. \(n \equiv 0 \pmod{12}\): Use the labeling from Case 1 for \(21 \leq i \leq \frac{3n}{4} – 5\), and then set: \[f(v_{\frac{3n}{4} – 4}) = F_{n-3}, \quad f(v_{\frac{3n}{4} – 1}) = F_n.\]
This completes the proof that \(\Gamma(n,\pm\{1,2,3\})\) is Fibonacci cordial precisely when \(n = 6\) or \(n \equiv 0,1,3 \pmod{4}\). ◻
Theorem 2.13. The circulant graph \(\Gamma(n,\pm\{1,2,3,4\})\) is Fibonacci cordial for all \(n > 8\).
Proof. First, note that \(\Gamma(9,\pm\{1,2,3,4\})\) is isomorphic to the complete graph \(K_9\), which is known to be Fibonacci cordial (see [6]). Therefore, it suffices to prove the result for \(n \geq 10\).
We first provide an explicit labeling for \(n = 10\) as a special case. Let \(f\) be the labeling function, then \(f(v_i)=F_{i}\) for \(0\le i\le 10\). This assignment generates cordial labeling. For \(n \geq 11\), we present a unified labeling strategy by dividing the cases based on \(n \pmod{3}\). In each case, we assign even-indexed Fibonacci numbers to a subset of the vertices. The remaining vertices can be labeled arbitrarily using unused odd Fibonacci numbers to ensure a Fibonacci cordial labeling.
Let \(f\) be the labeling function again, and let \(1 \leq i \leq k\), where \(k\) depends on \(n\) as described in each case below.
Case 1. \(n \equiv 0 \pmod{3}\).
\[f(v_i) = \begin{cases} F_{3(i-1)}, & \text{for } 1 \leq i \leq 4, \\ F_{9}, & \text{for } i = 7, \\ F_{3(2i + 3)/5}, & \text{for } i > 7 \text{ and } i \equiv 1 \pmod{5}, \\ F_{3(2i + 6)/3}, & \text{for } i > 7 \text{ and } i \equiv 2 \pmod{5}. \end{cases}\]
The index \(k\) is defined as: \[k = \begin{cases} \frac{5n – 9}{6}, & \text{if } n \equiv 3 \pmod{6}, \\ \frac{5n}{6} – 3, & \text{if } n \equiv 0 \pmod{6}. \end{cases}\]
Case 2. \(n \equiv 1 \pmod{3}\), \(n > 10\).
\[f(v_i) = \begin{cases} F_{3(i-1)}, & \text{for } 1 \leq i \leq 3, \\ F_{9}, & \text{for } i = 6, \\ F_{12}, & \text{for } i = 7, \\ F_{3(2i + 3)/5}, & \text{for } i > 7 \text{ and } i \equiv 1 \pmod{5}, \\ F_{3(2i + 6)/3}, & \text{for } i > 7 \text{ and } i \equiv 2 \pmod{5}. \end{cases}\]
The index \(k\) is given by: \[k = \begin{cases} \frac{5n – 23}{6}, & \text{if } n \equiv 1 \pmod{6}, \\ \frac{5n – 14}{6}, & \text{if } n \equiv 4 \pmod{6}. \end{cases}\]
Case 3. \(n \equiv 2 \pmod{3}\).
\[f(v_i) = \begin{cases} F_{3(i-1)}, & \text{for } 1 \leq i \leq 3, \\ F_{9}, & \text{for } i = 6, \\ F_{6i/5}, & \text{for } i > 6 \text{ and } i \equiv 0 \pmod{5}, \\ F_{3(2i + 3)/3}, & \text{for } i > 6 \text{ and } i \equiv 1 \pmod{5}. \end{cases}\]
The index \(k\) is given by: \[k = \begin{cases} \frac{5n – 10}{6}, & \text{if } n \equiv 2 \pmod{6}, \\ \frac{5n – 19}{6}, & \text{if } n \equiv 5 \pmod{6}. \end{cases}\]
Thus, in all cases for \(n \geq 10\), a Fibonacci cordial labeling exists. ◻
We conclude this section with an asymptotic conjecture regarding circulant graphs of the form \(\Gamma(n,S)\).
Conjecture 2.14. For large \(n\), almost every circulant graph \(\Gamma(n,S)\) with a “small” connection set \(S\) admits a Fibonacci cordial labeling.
In this paper, we explored the existence of Fibonacci cordial labelings for several significant families of graphs, including Generalized Petersen graphs, open and closed helm graphs, joint sum graphs, and circulant graphs of small order. These results contribute to the expanding field of graph labelings motivated by numerical sequences, particularly those derived from the Fibonacci sequence. Potential directions for future research include extending Fibonacci cordiality to larger circulant graphs with smaller connection sets and other Cayley graphs, including various graph products such as the lexicographic and corona products. Another promising direction involves investigating analogous labeling schemes based on other well-known sequences, such as the Tribonacci or Perrin numbers, with the aim of uncovering deeper structural or algebraic relationships within graph labeling theory.