A Fibonacci cordial (FC) labeling of a graph G is an injective function f : V(G) → {F0, F1, …, Fn}, where Fi is the ith Fibonacci number, such that the induced edge labeling f*(uv) = (f(u) + f(v)) (mod 2) satisfies |ef(0) − ef(1)| ≤ 1. A graph admitting such a labeling is called a Fibonacci cordial. First introduced by Rokad and Ghodasara (2016), FC labeling has been studied for several graph families. Mitra and Bhoumik (2020) extended this to complete graphs, cycles, and their corona (Cn and Kp for p ≤ 3). Motivated to build upon their work, we investigate Cn ⊙ Kp for p ≥ 4. Additionally, we examine whether the aforementioned family of corona graphs retains Fibonacci cordiality when alterations are made to the order of the corona, as observed in the family Kn ⊙ Cm. Moreover, we investigate the conditions under which two additional corona graph families, namely Km ⊙ Km and Kn, n ⊙ Kp, exhibit Fibonacci cordial labeling.
Graph labeling, an area of increasing interest within graph theory research, has witnessed significant growth and diversification over the past few decades. This field encompasses a range of techniques aimed at assigning labels to the elements of a graph, thereby facilitating the analysis and understanding of its structural properties and relationships. Graph labeling can broadly be categorized into three main types: vertex labeling, edge labeling, and total labeling, which incorporates both vertex and edge labeling approaches. Throughout our analysis, we employ standard graph-theoretic terminology and notations as outlined in Bondy and Murty [ 1 ].
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 v_f(0)-v_f(1)\vert \le 1\) , as well as \(\vert e_f(0)-e_f(1)\vert \le 1\) , where, \(v_f(i)\) and \(e_f(i)\) denote the number of vertices and edges labeled \(i\) , respectively, for \(i = 0,1\) .
This concept of cordial labeling, first introduced by Cahit [ 2 ], represents a seminal contribution to graph labeling theory. Initially explored through various vertex labeling strategies, cordial labeling has since been extended and adapted to encompass a diverse array of labeling schemes. These include divisor cordial labeling, product cordial labeling, total product cordial labeling, prime cordial labeling, and numerous others. Researchers seeking a comprehensive overview of the field often turn to Gallian’s extensive and dynamic survey [ 3 ].
Fibonacci cordial labeling emerges as a distinctive vertex labeling technique, leveraging the mathematical properties of the Fibonacci sequence to assign labels to the vertices of a graph. By integrating the Fibonacci sequence’s number-theoretic properties with the underlying structural characteristics of the graph family under investigation, this labeling approach aims to achieve cordiality within the labeled graph. This labeling is basically an extension of Cordial labeling, where we label the vertices with Fibonacci numbers instead of \(0\) and \(1\) . This version of cordial labeling is challenging compared to the original, as the number of odd and even vertex labels are not equal, whereas the induced edges of both parity must differ by at most \(1\) .
Definition 1.2. The sequence \(\{F_n\}\) of Fibonacci numbers is defined as the linear homogeneous recurrence relation of degree \(2\) : \[F_n = F_{n-1} + F_{n-2};\ \ F_0=0, F_1=F_2=1,\]
Lemma 1.3. In the set of Fibonacci numbers \(\{F_0, F_1, \dots, F_N\}\) , the number of even labels available is \(v_f(0) = \lfloor N/3 \rfloor + 1\) .
Proof. We prove by (strong form of) induction that \(F_n\) is even if and only if \(n \equiv 0 \pmod{3}\) . For the base cases, \(F_0=0\) , \(F_1=1\) , and \(F_2=1\) satisfy the hypothesis. Now for the inductive step, we assume the hypothesis holds for all \(m \le k\) . For \(F_{k+1} = F_k + F_{k-1}\) :
If \(k+1 = 3j\) , then \(k=3j-1\) and \(k-1=3j-2\) . Both are odd by hypothesis, so \(F_{k+1}\) is even.
If \(k+1 = 3j+1\) , then \(F_k\) is even and \(F_{k-1}\) is odd, so \(F_{k+1}\) is odd.
If \(k+1 = 3j+2\) , then \(F_k\) is odd and \(F_{k-1}\) is even, so \(F_{k+1}\) is odd.
Thus, exactly one out of every three labels is even, yielding \(\lfloor N/3 \rfloor + 1\) even labels. ◻
Definition 1.4. 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 e_f(0)-e_f(1)\vert \le 1\) .
Note that, unlike standard cordial labeling, the vertex parities \(v_f(0)\) and \(v_f(1)\) are determined by the properties of the Fibonacci sequence and are not required to be balanced, but rather should satisfy the Lemma 1.3.
Fibonacci cordial labeling was first introduced by Rokad \(\&\) Ghodasara [ 9 ]. In their work, they provide the results for the Petersen graph, Wheel graph, Shell graph, Bistar, and some product families of graphs (corona, etc.). Later in 2017, it was explored for more families of graphs by Rokad [ 8 ]. Continuous efforts were made by different researchers over the past few years to explore Fibonacci Cordiality among various families of graphs. In their recent paper [ 4 ], Mitra \(\&\) Bhoumik investigated the Fibonacci cordial labeling for the fundamental graphs, viz., complete graphs, cycles, and corona products of \(C_n\) and \(K_m\) , for \(m\le 3\) . In that paper they proposed the following theorem.
Theorem 1.5 ([ 4 ], Theorem 2.4).The complete list of Fibonacci cordial complete graphs are \(K_1, K_2, K_3, K_4, K_6, K_7\) , \(K_9, K_{11}, K_{18}\) , and \(K_{22}\) .
Continuous efforts were made by different researchers over the past decade to explore Fibonacci Cordiality among various families of graph [ 7 , 5 , 6 , 10 ]. In this paper, we are extending their work for the generalized family of \(C_n\odot K_m\) where \(m \ge 4\) . Further, we investigate another family, namely the corona of complete bipartite graphs with complete graphs i.e., \(K_{n,n} \odot K_p\) .
The rest of the paper is organized as follows: We provide a few results in Section 2 which will be referred to in the following sections. We discuss the results obtained on the corona families \(C_n\odot K_m\) and \(K_{n,n}\odot K_p\) in Section 3 and Section 4 respectively, followed by concluding remarks and future scope in Section 5.
Before presenting the main results, we establish a few preliminary lemmas and propositions that will be instrumental in the subsequent analysis.
Lemma 2.1. For any cordial labeling \(f\) of a cyclic graph \(C_n\) , the number of odd edges (edges labeled with \(1\) ) is always even, and satisfies the inequality \[e_f(1) \le 2\min\{v_f(0),v_f(1)\},\] where \(v_f(i)\) and \(e_f(i)\) denote the number of vertices and edges labeled \(i\) , respectively, for \(i = 0,1\) .
Proof. An edge is odd exactly when its endpoints receive different labels. Consider a walk around the cyclic graph \(C_n\) . Each odd edge flips the current label type. Since the walk returns to its starting point, the total number of flips must be even. Therefore, the number of odd edges is even.
For the upper bound, every vertex of the smaller parity class (say there are \(s=\min\{v_f(0),v_f(1)\}\) such vertices) is incident to at most two edges of the cycle, and each odd edge is incident to exactly one vertex of that smaller class. Hence, each of these \(s\) vertices can contribute at most two odd edges, giving \[e_f(1)\le 2s = 2\min\{v_f(0),v_f(1)\},\] as required. ◻
Lemma 2.2. Let \(K_n\) be a complete graph with \(n\) odd, say \(n=2m+1\) . For any labeling \(f\) that assigns parities to vertices, the number of odd edges \(e_f(1)\) is even.
Proof. Let \(p\) be the number of odd-labeled vertices (so \(n-p\) even-labeled vertices). An edge is odd exactly when it joins one odd-labeled and one even-labeled vertex, hence \[e_f(1)=p(n-p).\]
Since \(n\) is odd, \(p\) and \(n-p\) have opposite parity, so their product is even. Therefore \(e_f(1)\) is even. ◻
Lemma 2.3. Let \(G\) and \(H\) be two complete graphs of order \(m\) , and let \(f_0 : V(G \cup H) \to \{F_0, F_1, \dots, F_{2m}\}\) be a labeling such that \(G\) and \(H\) contain \(g\) and \(h\) vertices labeled with odd Fibonacci numbers, respectively, with \(g \ge h\) . Define \[\tilde{v}_i = |v_G(i) – v_H(i)| \quad \text{and} \quad \tilde{e}_i = |e_G(i) – e_H(i)|, \quad \text{for } i = 0,1.\]
Then, swapping \(x\) odd-labeled vertices from \(G\) with \(x\) even-labeled vertices from \(H\) increases (or decreases) \(\tilde{v}_1\) and correspondingly increases (or decreases) \(\tilde{e}_0\) .
Proof. Let \(f_1\) be the labeling obtained from \(f_0\) by swapping \(x\) odd vertices from \(G\) with \(x\) even vertices from \(H\) . After the swap, \(G\) has \(g – x\) odd vertices and \(H\) has \(h+x\) odd vertices. The number of edges labeled \(1\) under \(f_0\) is: \[e_{f_0}(1) =g(m – g) + h(m – h).\]
Under the labeling \(f_1\) , we have: \[e_{f_1}(1) = (g – x)(m – h – x) + (h + x)(m – g + x).\]
Clearly if \(g \not= h\) , as \(0<x\le g\) , \(e_{f_1}(1) > e_{f_0}(1)\) when \(x < g-h\) , and \(e_{f_1}(1) < e_{f_0}(1)\) if \(x > g-h\) . If \(x = g-h\) , then the swap will result in the same composition of blocks, so we do not consider this case. If \(g=h\) , then any value of \(x>0\) will result in \(e_{f_1}(1)\) being less than \(e_{f_0}(1)\) . ◻
Theorem 2.4. Let \(S\) be any collection of \(n\) complete graphs of order \(m\) , each labeled with a Fibonacci cordial labeling such that the total number of vertices labeled 0 across all graphs is \(v_f(0) = p\) . Let \(S_0\) be the specific collection of \(n\) graphs isomorphic to \(K_m\) , also with \(v_f(0) = p\) , where each graph (block) contains either \(\lceil \frac{p}{nm} \rceil\) or \(\lfloor \frac{p}{nm} \rfloor\) many even labeled vertices. Then, if \(S \ne S_0\) , the total number of odd-labeled edges in \(S_0\) exceeds that in \(S\) .
Proof. Let \(B\) be any block in \(S\) . Define \(r_B = v_B(0) – \lfloor \frac{p}{nm} \rfloor\) and \(q_B = \lfloor \frac{p}{nm} \rfloor – v_B(0)\) , representing the surplus or deficit of even-labeled vertices relative to the target distribution in \(S_0\) . Let \(\{ X_1, X_2, \dots, X_k \}\) be the blocks in \(S\) with fewer than \(\lfloor \frac{p}{nm} \rfloor\) even-labeled vertices (i.e., \(q_B > 0\) ), and after reindexing, assume \(q_{X_1} \le q_{X_2} \le \cdots \le q_{X_k}\) . Similarly, let \(\{ Y_1, Y_2, \dots, Y_j \}\) be the blocks in \(S\) with more than \(\lfloor \frac{p}{nm} \rfloor\) even-labeled vertices (i.e., \(r_B > 0\) ), and assume \(r_{Y_1} \ge r_{Y_2} \ge \cdots \ge r_{Y_j}\) .
Now, for each \(X_i\) , perform a series of vertex swaps to exchange \(q_{X_i}\) odd-labeled vertices from \(X_i\) with an equal number of even-labeled vertices from blocks in \(\{Y_1, \dots, Y_j\}\) , starting with the largest \(r_{Y_j}\) available. For example, swap as many vertices as possible between \(X_1\) and \(Y_1\) , then \(Y_2\) , and so on, until \(q_{X_1}\) is reduced to 0 or 1. Repeat this process for \(X_2, X_3, \dots, X_k\) , ensuring after each step that \(q_{X_i} \in \{0,1\}\) and \(r_{Y_i} = 0\) .
This redistribution transforms \(S\) into \(S_0\) , the unique configuration in which each block contains either \(\lfloor \frac{p}{nm} \rfloor\) or \(\lceil \frac{p}{nm} \rceil\) even-labeled vertices.
Finally, by Lemma 2.3, each such swap strictly increases the number of odd-labeled edges. Therefore, \(S_0\) contains more odd edges than \(S\) , completing the proof. ◻
The following Corollary can be derived from the above Theorem immediately.
Corollary 2.5. Let \(S\) be any set of \(n\) many \(K_{m}\) graph blocks and \(F = \{f_1, f_2 ,\cdots, f_t\}\) be the set of all possible unique injective vertex labeling (up to isomorphism) on \(S\) such that \(e_{f_i}(0)=p\) for all \(1 \le i \le t\) . Then there exists some \(f_M\) such that \(e_{f_i}(1) \le e_{f_M}(1)\) for all \(1 \le i \le t\) where \(i \not = M\) . Moreover, the resulting blocks of \(f_M\) will each contain either \(\lceil \frac{p}{nm} \rceil\) or \(\lfloor \frac{p}{nm} \rfloor\) many even nodes.
Lemma 2.6. Let \(S\) be any set of \(n\) many \(K_m\) graph blocks, where \(nm \equiv 0 \pmod{3}\) . The maximum total number of odd edges is achieved when the total number of even-labeled vertices \(q\) is maximized, specifically at \(q = \frac{nm}{3} + 1.\) This maximum occurs when \(n-1\) blocks contain \(\frac{m}{3}\) even vertices and one block contains \(\frac{m}{3}+1\) even vertices. Moreover, the total number of odd edges in \(S\) cannot exceed \[\frac{2nm^2}{9} + \frac{m}{3} – 1.\]
Proof. By Theorem 2.4, for any fixed total number \(q\) of even-labeled vertices in \(S\) , the number of odd edges is maximized when each block contains either \(\lceil q/n\rceil\) or \(\lfloor q/n\rfloor\) even vertices. Since \(nm \equiv 0 \pmod{3}\) , the number of available even Fibonacci labels among the \(nm\) distinct vertex labels equals \(\frac{nm}{3}\) or \(\frac{nm}{3}+1\) , depending on whether the final Fibonacci index is even. The larger value, \[q_{\max}=\frac{nm}{3}+1,\] is attainable under the Fibonacci cordial labeling constraints.
Because each block contributes \(x(m-x)\) odd edges when it contains \(x\) even vertices, and because the function \(x(m-x)\) is strictly increasing on \(0\le x\le m/2\) , the total number of odd edges increases with \(q\) as long as \(q \le nm/2\) . Since \(q_{\max}=\frac{nm}{3}+1 < nm/2\) , the maximum total number of odd edges occurs at \(q=q_{\max}\) .
For this value of \(q\) , we have \[\frac{q}{n} = \frac{m}{3} + \frac{1}{n},\] so the distribution required by Theorem 2.4 is that \((n-1)\) blocks contain \(\frac{m}{3}\) even vertices and one block contains \(\frac{m}{3}+1\) even vertices. We now compute the resulting number of odd edges: \[e_i(1)=\frac{m}{3}\cdot\frac{2m}{3}=\frac{2m^2}{9} \quad\text{for each of the $n-1$ identical blocks,}\] and for the exceptional block, \[e_j(1)=\left(\frac{m}{3}+1\right)\left(\frac{2m}{3}-1\right) =\frac{2m^2}{9}+\frac{m}{3}-1.\]
Therefore, \[e(1) = (n-1)\cdot\frac{2m^2}{9} +\left(\frac{2m^2}{9}+\frac{m}{3}-1\right) = \frac{2nm^2}{9} + \frac{m}{3} – 1.\]
This is the claimed upper bound. ◻
The following Proposition provides a critical refinement to the existing literature regarding complete graphs (see Theorem 1.5), and proves that \(K_{22}\) is not Fibonacci cordial.
Proposition 2.7. \(K_m\) is not Fibonacci cordial for \(m>18\) .
Proof. Let \(E_v = \lfloor m/3 \rfloor + 1\) be the maximum number of even Fibonacci numbers among \(F_0,\dots,F_{m-1}\) , and \(O_v = m – E_v\) the number of odd-labeled vertices. Now in \(K_m\) , the number of odd edges is \(e_f(1) = E_v O_v\) , and even edges is \(e_f(0) = \binom{m}{2} – E_v O_v\) . Thus, for Fibonacci cordiality, we require \(|e_f(1) – e_f(0)| \le 1\) , which simplifies to: \[\left|\binom{m}{2} – 2E_vO_v\right| \le 1.\]
Substituting \(E_v\) and \(O_v\) : \[\left|\frac{m(m-1)}{2} – 2\left(\left\lfloor \frac{m}{3}\right\rfloor + 1\right)\left(m – \left\lfloor \frac{m}{3}\right\rfloor – 1\right)\right| \le 1.\]
Direct computation shows this inequality fails for \(m \ge 21\) . For \(m = 19, 20\) , exhaustive verification confirms the condition is also violated. Thus \(K_m\) is not Fibonacci cordial for \(m > 18\) . ◻
The corona \(G_1\odot G_2\) of two graphs is the graph obtained by taking one copy of \(G_1\) , and \(p_1\) copies of \(G_2\) (where \(\vert V(G_1)\vert=p_1\) ), and then joining the \(i^{\rm th}\) vertex of \(G_1\) by an edge to every vertex in the \(i^{\rm th}\) copy of \(G_2\) . The number of vertices of \(C_n\odot K_m\) is \(n(m+1)\) , and the number of edges is \(n \binom{m}{2}+nm+n=n(m(\frac{m+1}{2})+1)\) . In the graph \(G=C_n\odot K_m\) , let \(V=\{v_i^t\vert i\in \N\}\) , where \(t=0\) denotes the vertices of \(C_n\) (we refer to them as inner vertices), and \(t\in \Z_m^{+}\) represent the vertices that do not lie on the cycle. We refer to them as outer vertices. We can identify the \(G=C_{n}\odot K_{m}\) as \(n\) many \(K_{m+1}\) graphs where all the complete graphs are like pendants, and connected by a closed string ( \(C_n\) ). Throughout the paper, we will follow these notations:
We call each complete subgraph \(K_{m+1}\) of \(G\) a block of \(G\) .
We denote the \(i^{\rm th}\) block by \(K_{m+1}^i\) .
For any induced subgraph \(H\) of \(G\) , the number of even edges is denoted by \(e_H(0)\) , analogously \(e_H(1)\) denote the number of odd degrees.
\(e_H(1)-e_H(0)\) will be denoted as \(\tilde{e}_H\) .
Theorem 3.1. \(C_{n}\odot K_{4}\) is not Fibonacci cordial when \(n \equiv 2 \pmod{4}\) .
Proof. The graph \(C_{n}\odot K_{4}\) consists of an inner cycle \(C_n\) where a \(K_5\) block is attached at each cycle node. The total number of edges in this corona graph is \(|E| = 11n\) . For the graph to be Fibonacci cordial, the number of odd edges \(e_f(1)\) must satisfy the condition \(|e_f(0) – e_f(1)| \le 1\) . Since \(|E| = 11n\) is even when \(n \equiv 2 \pmod{4}\) , cordiality requires \(e_f(1) = \frac{11n}{2}\) . Because \(n = 4k + 2\) for some integer \(k\) , we have: \[e_f(1) = \frac{11(4k + 2)}{2} = 22k + 11.\]
This target value for \(e_f(1)\) is an odd number.
We now analyze the structural parity of \(e_f(1)\) . Let \(e_{K_5^i}(1)\) denote the total number of odd edges within each of the \(n\) blocks \(\{K_5^1, K_5^2, \dots, K_5^n\}\) . By Lemma 2.2, for any complete graph \(K_p\) where \(p\) is odd, the number of odd edges \(e_{K_p}(1)\) is always even. Since each block in this graph is a \(K_5\) , every block must contribute an even number of odd edges. Consequently, the total number of odd edges across all \(n\) blocks, \(\sum_{i=1}^n e_{K_5^i}(1)\) , is a sum of even numbers and is therefore even.
Furthermore, by Lemma 2.1, the number of odd edges in the inner cycle \(C_n\) , denoted \(e_{C_n}(1)\) , is always even. The total number of odd edges in the entire graph is the sum of these two components: \[e_f(1) = \sum_{i=1}^n e_{K_5^i}(1) + e_{C_n}(1).\]
Since each pf \(e_{K_5^i}(1)\) and \(e_{C_n}(1)\) are even, their sum \(e_f(1)\) must be even. This contradicts the requirement that \(e_f(1)\) must be an odd number ( \(22k + 11\) ). Thus, no Fibonacci cordial labeling exists for \(n \equiv 2 \pmod{4}\) . ◻
Theorem 3.2. \(C_{n}\odot K_{4}\) is Fibonacci cordial when \(n \not\equiv 2\ (\mod 4)\) .
Proof. There are \(5n\) many vertices and \(11n\) many edges in the corona graph \(C_{n}\odot K_{4}\) . The graph consists of a cycle \(C_n\) inside, and at each cycle node, a \(K_5\) is attached, which we consider as a block. All possible parity assignments for a \(K_{5}\) block yield the following imbalances: \[\begin{array}{c|c|c|c} (v(0),v(1)) & e(1) & e(0) & \tilde{e} \\ \hline (0,5),(5,0) & 0 & 10 & 10 \\ (1,4),(4,1) & 4 & 6 & 2 \\ (2,3),(3,2) & 6 & 4 & 2 \end{array}\]
Thus the minimum achievable imbalance in \(K_{5}\) is \(2\) , attained whenever \(v(0)\in\{1,2,3,4\}\) . Among these, the assignments using the fewest even labels are \(v(0)=1\) and \(v(0)=2\) , corresponding exactly to the Type II and Type I blocks in Figure 1. Using only these two block types therefore minimizes even-label usage while achieving the optimal imbalance.
We will now approach this analysis through cases. It’s notable that any node within a \(C_{n}\odot K_{4}\) block can be selected to be part of the inner cycle. As both Type I and Type II blocks comprise at least one odd and one even node, the inner cycle of any \(C_{n}\odot K_{4}\) graph exclusively composed of Type I or Type II blocks can accommodate any combination of odd and even nodes. By Lemma 2.1, a cycle can feature any even number of odd edges if there are no constraints on the quantity of odd and even nodes within the cycle.
Table 1 lists for each case of \(n \pmod{12}\) the distribution of Type I and Type II blocks, alongside cycle edge parities required for Fibonacci cordiality. The \(n\) blocks are partitioned into Type I (2 even nodes, 3 odd nodes) and Type II (1 even node, 4 odd nodes) to manage the consumption of even Fibonacci labels. According to Lemma 1.3, the number of even labels available in the set \(\{F_0, F_1, \dots, F_{N}\}\) is exactly \(\lfloor N/3 \rfloor + 1\) .
Consider the case \(n \equiv 0 \pmod{12}\) , where \(n = 12q\) for some \(q \in \mathbb{N}\) . The graph order is \(|V| = 60q\) , and the labels used are \(\{F_0, \dots, F_{60q}\}\) . By the inductive result in Lemma 1.3, the available labels consist of \(\lfloor (60q)/3 \rfloor + 1 = 20q+1\) even labels and \((60q+1) – (20q+1) = 40q\) odd labels. Assigning \(8q\) Type I blocks and \(4q\) Type II blocks requires exactly \(8q(2) + 4q(1) = 20q\) even labels and \(8q(3) + 4q(4) = 40q\) odd labels. As these requirements are within the available parity counts, injectivity is preserved. Regarding edge balance, this configuration yields \(8q(6) + 4q(4) = 64q\) odd edges and \(8q(4) + 4q(6) = 56q\) even edges within the blocks. With \(10q\) even and \(2q\) odd cycle edges (permitted by Lemma 2.1 as \(2q\) is even), the total edge counts are \(e_f(1) = 64q + 2q = 66q\) and \(e_f(0) = 56q + 10q = 66q\) . Thus, \(|e_f(0) – e_f(1)| = 0\) , satisfying the cordiality condition. The remaining cases in Table 1 follow a similar verification of label availability and edge balance. ◻
| Cases | \(n\) | Type I | Type II | Cycle Even | Cycle Odd |
|---|---|---|---|---|---|
| \(n\equiv 0 \pmod{12}\) | \(12q\) | \(8q\) | \(4q\) | \(10q\) | \(2q\) |
| \(n\equiv 4 \pmod{12}\) | \(12q+4\) | \(8q+3\) | \(4q+1\) | \(10q+4\) | \(2q\) |
| \(n\equiv 8 \pmod{12}\) | \(12q+8\) | \(8q+6\) | \(4q+2\) | \(10q+8\) | \(2q\) |
| \(n\equiv 9 \pmod{12}\) | \(12q+9\) | \(8q+6\) | \(4q+3\) | \(10q+7\) | \(2q+2\) |
| \(n\equiv 1 \pmod{12}\) | \(12q+1\) | \(8q+1\) | \(4q\) | \(10q+1\) | \(2q\) |
| \(n\equiv 5 \pmod{12}\) | \(12q+5\) | \(8q+4\) | \(4q+1\) | \(10q+5\) | \(2q\) |
| \(n\equiv 3 \pmod{12}\) | \(12q+3\) | \(8q+2\) | \(4q+1\) | \(10q+3\) | \(2q\) |
| \(n\equiv 7 \pmod{12}\) | \(12q+7\) | \(8q+5\) | \(4q+2\) | \(10q+7\) | \(2q\) |
| \(n\equiv 11 \pmod{12}\) | \(12q+11\) | \(8q+8\) | \(4q+3\) | \(10q+11\) | \(2q\) |
Theorem 3.3. \(C_{n}\odot K_{5}\) is Fibonacci cordial for all \(n\) .
Proof. There are \(6n\) vertices and \(16n\) edges in the graph, i.e. \(|V(C_{n}\odot K_{5})|=6n\) and \(|E(C_{n}\odot K_{5})|=16n\) . The set of Fibonacci numbers used are \(\{ F_0, F_1, \cdots, F_{6n} \}\) , which implies there are \(2n+1\) many even Fibonacci labels (by Lemma 1.3) and \(4n\) many odd Fibonacci labels available to be assigned to the vertices.
In each block \(K_6\) , we assign two even and four odd labels (as shown in Figure 2 in such a manner that all the vertices in the cycle will be assigned labels of same parity ( all odd labels or all even labels). Hence, during the assignment, total \(2n\) even Fibonacci numbers and \(4n\) odd Fibonacci numbers are used. As a result, total \(8n\) odd edges (from the blocks) and \(8n\) even edges ( \(7n\) from the blocks and \(n\) from the cycle). ◻
Theorem 3.4. \(C_{n}\odot K_{6}\) is not Fibonacci cordial when \(n\) is an odd number.
Proof. \(|V(C_{n}\odot K_{6})|=7n\) and \(|E(C_{n}\odot K_{6})|=22n\) , which implies for any value of \(n\) , total number of edges in the corona graph is \(22n\) , an even number. If \(C_{n}\odot K_{6}\) is Fibonacci Cordial, then the induced edge labeling must generate \(11n\) many edges of each parity. If \(n\) is odd, then we need a total \(11n\) i.e., an odd number of odd edges which is impossible to achieve due to the results described in Lemma 2.1. This completes the proof. ◻
The above theorem indicates that if \(C_{n}\odot K_{6}\) is Fibonacci Cordial, then \(n\) must be even. Therefore, we investigate the following three cases viz. \(n \equiv 0 \ ( \mod 6 )\) , \(n \equiv 2 \ ( \mod 6 )\) , and \(n \equiv 4 \ ( \mod 6 )\) . We consider three different patterns of assignment of the odd and even labels to the nodes of the blocks (i.e., \(K_7\) ) as shown in Figure 3. In Type I, II, and III one, two, and three vertices are labeled with even labels, and hence six, five, and four vertices are assigned odd labels respectively. As a result, the respective induced functions have 6 odd edges and 15 even edges in Type I, 10 odd edges and 11 even edges in Type II, and 12 odd and 9 even edges in Type III blocks.
Theorem 3.5. \(C_n \odot K_6\) is Fibonacci Cordial if \(n \equiv 0\ (\mod 2)\)
Proof. Fibonacci Cordial graph labeling when \(n \equiv 0,2\) or \(4\ (\mod 6)\) , i.e. \(n=6p, 6p+2\) , or \(6p+4\) for some \(p \in \mathbb{N}\) , will be induced using combinations of three types of \(K_7\) graph blocks. Type I, II, and III blocks will contain one, two, and three even nodes respectively.
When \(n \equiv 0\ (\mod 6)\) , we will assign \(4p\) many blocks as Type II and \(2p\) many as Type III. When \(n \equiv 2\ (\mod 6)\) , we will assign \(p\) many blocks as Type I, \(2p+1\) many as Type II, and \(3p+1\) many as Type III. And when \(n \equiv 4\ (\mod 6)\) , we will assign \(p\) many blocks as Type I, \(2p+2\) many as Type II, and \(3p+2\) many as Type III.
As an example, for the case of \(n \equiv 0\ (\mod 6)\) , \(|V| = 42p\) , implying that \(28p\) and \(14p+1\) many odd and even node labels are available (Lemma 1.3). We will assign \(4p\) many blocks as Type II and \(2p\) many as Type III. The induced edge labeling results in \(64p\) many odd and \(62p\) many even edges in the blocks. Therefore, if \(4p\) cycle edges are even and \(2p\) cycle edges are odd, allowed by Lemma, total odd and even edges in the graph will both equal \(66q\) . Given the assignments previously provided, the remaining two cases can similarly be shown to result in Fibonacci Cordial Labeling. ◻
We conclude this section by examining the Fibonacci cordiality of the corona product \(C_n \odot K_p\) for large values of \(p\) . In particular, we identify specific conditions under which this family fails to admit a Fibonacci cordial labeling.
Theorem 3.6. The corona graph \(C_n \odot K_p\) is not Fibonacci cordial for \(p \ge 13\) .
Proof. The total number of edges in \(C_n \odot K_p\) is \(|E| = \frac{n(p^2+p+2)}{2}\) . For Fibonacci cordiality, the number of odd edges \(e_f(1)\) must satisfy \(e_f(1) \in \{\lfloor |E|/2 \rfloor, \lceil |E|/2 \rceil\}\) . Thus, \(e_f(1) \approx \frac{n(p^2+p+2)}{4}\) .
The maximum number of odd edges available is the sum of the maximum odd edges from \(n\) blocks of order \(p+1\) and the cycle \(C_n\) . By Lemma 2.6, the maximum odd edges in a block \(K_{p+1}\) is given by \(M(p) = \frac{2(p+1)^2}{9} + \frac{p+1}{3} – 1\) . Since the cycle contributes at most \(n\) odd edges, Fibonacci cordiality is only possible if: \[\frac{n(p^2+p+2)}{4} \le n \left( \frac{2(p+1)^2}{9} + \frac{p+1}{3} – 1 \right) + n.\]
Dividing by \(n\) and simplifying the quadratic inequality in terms of \(p\) : \[\begin{align*} \frac{p^2+p+2}{4} \le& \frac{2p^2 + 7p + 5}{9}\\ 9p^2 + 9p + 18 \le& 8p^2 + 28p + 20\\ p^2 – 19p – 2 \le& 0. \end{align*}\]
This inequality fails for all \(p \ge 20\) . For \(13 \le p \le 19\) , direct verification of the exact \(e_f(1)\) requirement and available Fibonacci parities confirms that no cordial labeling exists. ◻
Theorem 3.7. The corona graph \(C_n \odot K_p\) is not Fibonacci cordial in each of the following cases:
(a) When \(n\) is odd and \(p \equiv 6 \pmod{8}\) .
(b) When \(p \ge 13\) .
Proof.
Case 1. Let \(p = 8k + 6\) for some integer \(k\) , and suppose \(n\) is odd. Then the total number of edges in \(C_n \odot K_p\) is: \[|E| = n \cdot \left\{\frac{(8k + 6)(8k + 7)}{2} + 1 \right\} = n(32k^2 + 52k + 22).\]
In order to \(C_n \odot K_{8k+6}\) be Fibonacci cordial, the edge labels with \(0\) and \(1\) must occur equally, implying the number of edges labeled \(1\) must be: \[e_f(1) = \frac{|E|}{2} = n(16k^2 + 26k + 11).\]
This expression is odd when \(n\) is odd, contradicting Lemma 2.1, which states that the number of odd edges in a cycle (and thus in \(C_n\) ) must be even. Hence, no such labeling is possible.
Case 2. The total number of edges for the graph \(C_n \odot K_p\) is \(\frac{n(p^2+p+2)}{2}\) . For Fibonacci Cordiality, the required number of odd edges is approximately \[e(1) \approx \frac{|E(G)|}{2} = \frac{n(p^2+p+2)}{4}.\]
The maximum available odd edges is the sum of the maximum odd edges from \(n\) blocks \(K_{p+1}\) and the cycle \(C_n\) . Using the maximization principle from Lemma 2.6 for the blocks ( \(K_{p+1}\) ) and noting \(e_{C_n}(1) \le n\) , the Fibonacci labeling is only possible when, \[\frac{n(p^2+p+2)}{4}\le \left( \frac{2n(p+1)^2}{9} + \frac{p+1}{3} – 1 \right) + n.\]
This inequality holds for \(n \ge 3\) and \(1\le p\le 12\) , thus establishing the result.
◻
Example 3.8. We now provide an explicit example of \(C_3 \odot K_4\) to demonstrate the Fibonacci cordial labeling construction. The graph order is \(|V| = 5n = 15\) , and we assign labels from the set \(\{F_0, F_1, \dots, F_{15}\}\) . According to Lemma 1.3, the number of available even Fibonacci labels in this set is \(v_f(0) = \lfloor 15/3 \rfloor + 1 = 6\) , and the number of odd labels is \(v_f(1) = 16 – 6 = 10\) .
Per Table 1, for the case \(n=3\) , we utilize two Type I blocks and one Type II block. The vertex parity distribution is assigned as follows:
Type I blocks ( \(K_5^1, K_5^2\) ) : 2 even vertices and 3 odd vertices each.
Type II block ( \(K_5^3\) ) : 1 even vertex and 4 odd vertices.
The total number of even vertices required is \(2(2) + 1(1) = 5\) , which is within the available limit of 6 even labels. We define the specific assignment of even Fibonacci labels to vertices \(v_j^i\) (where \(i\) is the block index and \(j\) is the vertex index within the block) as follows: \[f(v_0^1)=F_0, \quad f(v_1^1)=F_3, \quad f(v_0^2)=F_6, \quad f(v_1^2)=F_9, \quad f(v_0^3)=F_{12} .\]
The remaining 10 vertices are assigned the available odd Fibonacci labels from the set \(\{F_1, F_2, F_4, F_5, F_7, F_8, F_{10}, F_{11}, F_{13}, F_{14}\}\) injectively. Regarding the induced edge labeling:
Each Type I block generates 6 odd edges and 4 even edges.
The Type II block generates 4 odd edges and 6 even edges.
By assigning the inner cycle \(C_3\) vertices such that they are all even (e.g., vertices \(v_0^1, v_0^2, v_0^3\) ), the cycle contributes 0 odd edges and 3 even edges.
The resulting total edge counts are \(e_f(1) = 6 + 6 + 4 + 0 = 16\) and \(e_f(0) = 4 + 4 + 6 + 3 = 17\) . Thus, \(|e_f(0) – e_f(1)| = 1\) , which satisfies the condition for Fibonacci cordiality.
Theorem 4.1. \(K_{m_1,m_2}\) is Fibonacci cordial if either \(m_i\) is even and \(m_i\le 2m_j\) or \(m_1+m_2\le 12\) where both \(m_i\) is odd.
Proof. Let us denote the vertices of \(K_{m_1,m_2}\) by \(\{v_{11},v_{12},\cdots,v_{1m},v_{21},v_{2},\cdots,v_{2n}\}\) . In order to make \(K_{m_1,m_2}\) Fibonacci cordial, let us label \(p_i\) many vertices of \(\{v_{ij}\}\) by even Fibonacci labels, and the rest by odd.
\(e_f(1)=p_1(m_2-p_2)+p_2(m_1-p_1)\) and \(e_f(0)=p_1p_2+(m_1-p_1)(m_2-p_2)\) , we get \[\begin{equation} e_f(1)-e_f(0)= (2p_1-m_1)(m_2-2p_2), \end{equation} \tag{1}\] upon simplification. Thus \(\vert e_f(1)-e_f(0) \vert \le 1\) if either \(m_i=2p_i\) or \(\vert m_1-2p_1 \vert = 1 =\vert m_2-2p_2 \vert\) .
First, we consider the former case. Without loss of generality, we consider the case where \(m_1\) is even, and \(m_1/2\) of them are labeled with even Fibonacci labels. As there are \(\lfloor (m_1+m_2)/3\rfloor +1\) , many even labels, \(m_1/2\le \lfloor (m_1+m_2)/3\rfloor +1\le (m_1+m_2)/3 +1\) , which implies that \(m_1\le 2m_2+6\) .
Now for the later case, as \(m_i=2p_i \pm 1\) , \(p_1 +p_2\le \lfloor (m_1+m_2)/3\rfloor +1\le (2k_1+2k_2+2)/3 +1\) , which simplifies to \(p_1+p_2\le 5\) , and consequently \(m_1+m_2\le 12\) . ◻
The corona graph \(K_{n,n} \odot K_p\) consists of an inner complete bipartite graph \(K_{n,n}\) where each of the \(2n\) vertices is identified with one vertex of a \(K_{p+1}\) block. This structure can be viewed as comprising two columns, each containing \(n\) copies of the graph \(K_{p+1}\) . We refer to each such copy of \(K_{p+1}\) as a block, and to the two groups of \(n\) blocks as the left and right columns, corresponding to the two partite sets of \(K_{n,n}\) . The total number of vertices and edges is given by: \(|V(G)| = 2n(p + 1)\) , \(|E(G)| = 2n \binom{p+1}{2} + n^2 = np(p+1) + n^2\) . Following the structural notation established in the previous section, we define the vertex set of the corona graph \(G = K_{n,n} \odot K_p\) as: \[V = \{v_{i,j,k} \mid 1 \le i \le 2, 1 \le j \le n, 0 \le k \le p\},\] where \(k=0\) denotes the root vertices belonging to the base bipartite graph \(K_{n,n}\) , and \(k \in \{1, \dots, p\}\) represents the outer vertices of the \(p\) -order complete graphs attached to each root. The index \(i\) partitions the graph into two columns, with \(i=1\) and \(i=2\) representing the left and right partite sets, respectively. Finally, \(j\) denotes the specific level or row within each partite set.
Theorem 4.2. \(K_{n,n} \odot K_1\) is Fibonacci Cordial for all \(n \in \mathbb{N}\) .
Proof. This graph was examined in six cases based on the value of \(n\) . For each case, we have provided an assignment of nodes and edges that produces a Fibonacci Cordial graph. For the first case, as an example, we have shared the calculations that prove its Fibonacci Cordiality. The proofs of the other five cases can be calculated in the same manner.
Case 1. \(n \equiv 0 \pmod 6\) , i.e. \(n=6x\) for some \(x \in \mathbb{N}\) . This implies there are \(24x\) vertices and \(36x^2 + 12x\) edges. Therefore, \(8x+1\) many even Fibonacci numbers (by Lemma 1.3) and \(16x\) many odd Fibonacci numbers to be used as vertex labels. In each column of the bipartite graph, we will assign \(3x\) many nodes as odd and \(3x\) many nodes as even. Labels for the leaf nodes connected to each node in the left column of the bipartite graph are as follows: \(x\) many will be even leaf nodes connected to even nodes in the left column, \(x\) many will be even leaf nodes connected to odd nodes in the left column, \(2x\) will be odd leaf nodes connected to even nodes in the left column, and \(2x\) will be odd leaf nodes connected to odd nodes in the left column. Each leaf node connected to a node in the right column of the bipartite graph will be labeled odd. The induced node labeling generates: \(v_{f}(1)=16x\) and \(v_{f}(0)=8x\) . While these vertex parities are not balanced, they are within the available limits of the Fibonacci sequence indices as established in Lemma 1.3. Because the induced edge labeling results in \(e_{f}(1) = e_{f}(0) = 18x^{2} + 6x\) , the edge-balance condition \(|e_f(0) – e_f(1)| \le 1\) for Fibonacci cordiality is strictly satisfied.
Case 2. \(n \equiv 1 \pmod 6\) i.e. \(n=6x+1\) for some \(x \in \mathbb{N}\) . In each column of the bipartite graph, we will assign \(3x+1\) nodes as odd and \(q\) nodes as even. Labels for the leaf nodes connected to each node in the left column of the bipartite graph are as follows: \(x\) many will be even leaf nodes connected to even nodes in the left column, \(x-1\) many will be even leaf nodes connected to odd nodes in the left column, \(2x\) will be odd leaf nodes connected to even nodes in the left column, and \(2x+2\) will be odd leaf nodes connected to odd nodes in the left column. Finally, each leaf node connected to a node in the right column of the bipartite graph will be labeled odd.
Case 3. \(n \equiv 2 \pmod 6\) i.e. \(n=6x+2\) for some \(x \in \mathbb{N}\) . In the left column of the bipartite graph, we will assign \(3x+2\) many nodes as odd and \(3x\) many nodes as even. In the right column of the bipartite graph, we will assign \(3x+1\) many nodes as odd and \(3x+1\) many nodes as even. Labels for the leaf nodes connected to each node in the left column of the bipartite graph are as follows: \(x\) many will be even leaf nodes connected to even nodes in the left column, \(x+1\) many will be even leaf nodes connected to odd nodes in the left column, \(2x\) many will be odd leaf nodes connected to even nodes in the left column, and \(2x+1\) many will be odd leaf nodes connected to odd nodes in the left column. Finally, each leaf node connected to a node in the right column of the bipartite graph will be labeled odd.
Case 4. \(n \equiv 3 \pmod 6\) i.e. \(n=6x+3\) for some \(x \in \mathbb{N}\) . In each column of the bipartite graph, we will assign \(3x+2\) many nodes as odd and \(3x+1\) many nodes as even. Labels for the leaf nodes connected to each node in the left column of the bipartite graph are as follows: \(x+1\) many will be even leaf nodes connected to even nodes in the left column, \(x\) many will be even leaf nodes connected to odd nodes in the left column, \(2x\) many will be odd leaf nodes connected to even nodes in the left column, and \(2x+2\) many will be odd leaf nodes connected to odd nodes in the left column. Finally, each leaf node connected to a node in the right column of the bipartite graph will be labeled odd.
Case 5. \(n \equiv 4 \pmod 6\) i.e. \(n=6x+4\) for some \(x \in \mathbb{N}\) . In each column of the bipartite graph, we will assign \(3x+2\) many nodes as odd and \(3x+2\) many nodes as even. Labels for the leaf nodes connected to each node in the left column of the bipartite graph are as follows: \(x+1\) many will be even leaf nodes connected to even nodes in the left column, \(x+1\) many will be even leaf nodes connected to odd nodes in the left column, \(2x+1\) many will be odd leaf nodes connected to even nodes in the left column, and \(2x+1\) many will be odd leaf nodes connected to odd nodes in the left column. Finally, each leaf node connected to a node in the right column of the bipartite graph will be labeled odd.
Case 6. \(n \equiv 5 \pmod 6\) i.e. \(n=6x+5\) for some \(x \in \mathbb{N}\) . In each column of the bipartite graph, we will assign \(3x+3\) many nodes as odd and \(3x+2\) many nodes as even. Labels for the leaf nodes connected to each node in the left column of the bipartite graph are as follows: \(x+1\) many will be even leaf nodes connected to even nodes in the left column, \(x\) many will be even leaf nodes connected to odd nodes in the left column, \(2x+1\) will be odd leaf nodes connected to even nodes in the left column, and \(2x+3\) will be odd leaf nodes connected to odd nodes in the left column. Finally, each leaf node connected to a node in the right column of the bipartite graph will be labeled odd.
◻
Theorem 4.3. \(K_{n,n} \odot K_2\) is Fibonacci Cordial if \(n \equiv 0 \pmod 2\)
Proof. Let us assume that \(n \equiv 0\ (\mod 2)\) , i.e., \(n=2q\) for some \(q \in \mathbb{N}\) . This implies there are \(12q\) vertices and \(4q^{2} + 12q\) edges. Therefore, \(4q+1\) many even Fibonacci numbers (by Lemma 1.3) and \(8q\) many odd Fibonacci numbers to be used as vertex labels. Let each block in the left column be Type I and let each block in the right column be Type II, as shown in Figure 4.
Type I consists of only odd nodes, so each block in the left column will have an odd node included in the bipartite graph. Type II consists of one odd and two even nodes, so each Type II block can have either an odd or an even node included in the bipartite graph. Let \(\frac{n-2}{2}\) many blocks in the right column have an odd node included in the bipartite graph, and \(n- \frac{n-2}{2}\) many have an even node included in the bipartite graph. The induced node labeling generates: \(v_f(1):=4n\) and \(v_f(1):=2n\) . These values are within the available limits. The induced edge labeling generates: total odd edges in the blocks as \(0 + 2n = 2n\) , total even edges in the blocks as \(3n + n = 4n\) , total odd edges in the bipartite graph as \(n (n-\frac{n(n-2)}{2} )\) , and total even edges in the bipartite graph as \(\frac{n(n-2)}{2}\) , resulting in \(\frac{n^2+6n}{2}\) total odd edges and \(\frac{n^{2}+6n}{2}\) total even edges. This ensures that the defined labeling satisfies all the conditions of Fibonacci cordial labeling. ◻
Theorem 4.4. \(K_{n,n} \odot K_3\) is Fibonacci Cordial for all \(n\) .
Proof. In this graph, the total number of vertices and edges are given by \(|V(K_{n,n} \odot K_3)|=8n\) and \(|E(K_{n,n} \odot K_3)|=n^{2}+12n\) respectively. In this case, each block forms \(K_4\) . The assignment of the vertex labels to the \(2n\) many blocks is a combination of two types I and II as shown in Figure 5. There are three other possible arrangements of vertex labels to the blocks but we consider these two as they give rise to 3 edges of each parity and hence it is already balanced. To achieve Fibonacci cordial-ness it is sufficient to balance the induced edges in the bipartite graph. If \(n\) is even then the left column has \(\frac{n}{2}\) even nodes and \(\frac{n}{2}\) odd nodes and the right column assignment is insignificant. If \(n\) is odd then the left column has \(\frac{n+1}{2}\) even nodes and \(\frac{n-1}{2}\) odd nodes and the right column has \(\frac{n-1}{2}\) odd nodes and \(\frac{n+1}{2}\) even nodes. The blocks are complete graphs, so their orientation can be determined to achieve the desired number of odd vertices and even vertices on the columns of the bipartite graph. We discuss the following six cases.
Case 1. Let \(n \equiv 0~(\bmod \ 6)\) then \(n =6q\) for some \(q \in \mathbb{N}\) .
Consequently, \(|V(K_{n,n} \odot K_3)|=48q\) and \(|E(K_{n,n} \odot K_3)|=36q^{2}+72q\) . Thus, there are \(16q+1\) many even (proceeds from Lemma 1.3) and \(32q\) many odd Fibonacci numbers available to be used for vertex labeling. Among the \(12q\) blocks, \(10q\) are of Type I, and \(2q\) are of Type II.This results in \(v_f(0)=16q\) and \(v_f(1)=32q\) , both falling within the intended limits.
There are \(3q\) even and \(3q\) odd nodes on both the columns of the bipartite graph. Consequently, we have \(e_f(0) = e_f(1) =18q^{2}+36q\) which satisfies the condition \(\vert e_f(0)-e_f(1)\vert \le 1\) as required.
Case 2.Let \(n \equiv 1~(\bmod \ 6)\) then \(n =6q+1\) for some \(q \in \mathbb{N}\) .
This implies \(|V(K_{n,n} \odot K_3)|=48q+8\) and \(|E(K_{n,n} \odot K_3)|=36q^{2}+84q+13\) . So, there are \(16q+3\) many even and \(32q+6\) many odd Fibonacci numbers available to be used for vertex labeling. Out of a total \(12q+2\) blocks, \(10q+2\) are of Type I, and \(2q\) are of Type II.This leads to \(v_f(0)=16q+2\) and \(v_f(1)=32q+6\) . Observe that both these values are within the intended limits.
As per the description of the assignment, there are \(3q+1\) even and \(3q\) odd nodes on the left column and \(3q+1\) odd and \(3q\) even nodes on the right column of the bipartite graph. As a result, we have \(e_f(0) = e_f(1) =18q^{2}+42q+6\) which fulfills the condition \(\vert e_f(0)-e_f(1)\vert \le 1\) as stipulated.
Case 3.Let \(n \equiv 2~(\bmod \ 6)\) then \(n =6q+2\) for some \(q \in \mathbb{N}\) .
Then \(|V(K_{n,n} \odot K_3)|=48q+16\) and \(|E(K_{n,n} \odot K_3)|=36q^{2}+96q+28\) . So, there are \(16q+6\) many even and \(32q+11\) many odd Fibonacci numbers available to be used for vertex labeling. Out of a total of \(12q+4\) blocks, \(10q+3\) are of Type I, and \(2q+1\) are of Type II.This leads to \(v_f(0)=16q+6\) and \(v_f(1)=32q+10\) , both satisfying the intended limits. As per the assignment, \(3q+1\) even and \(3q+1\) odd nodes on both the columns of the bipartite graph. As a result, we have \(e_f(0) = e_f(1) = 18q^{2}+48q+14\) which satisfies the condition \(\vert e_f(0)-e_f(1)\vert \le 1\) as required.
Case 4.Let \(n \equiv 3~(\bmod \ 6)\) then \(n =6q+3\) for some \(q \in \mathbb{N}\) .
Then \(|V(K_{n,n} \odot K_3)|=48q+24\) and \(|E(K_{n,n} \odot K_3)|=36q^{2}+108q+45\) . Consequently, there are \(16q+9\) many even and \(32q+16\) many odd Fibonacci numbers available to be used for vertex labeling. Out of a total of \(12q+6\) blocks, \(10q+5\) are of Type I, and \(2q+1\) are of Type II.This leads to \(v_f(0)=16q+8\) and \(v_f(1)=32q+16\) . Observe that both these values are within the intended limits.
There are \(3q+2\) even and \(3q+1\) odd nodes on the left column and \(3q+2\) odd and \(3q+1\) even nodes on the right column of the bipartite graph. As a result, we have \(e_f(0)=18q^{2}+54q+22\) and \(e_f(1)=18q^{2}+54q+23\) which fulfills the condition \(\vert e_f(0)-e_f(1)\vert \le 1\) as stipulated.
Case 5.Let \(n \equiv 4~(\bmod \ 6)\) then \(n =6q+4\) for some \(q \in \mathbb{N}\) .
This implies \(|V(K_{n,n} \odot K_3)|=48q+32\) and \(|E(K_{n,n} \odot K_3)|=36q^{2}+96q+28\) . So, there are \(16q+11\) many even and \(32q+22\) many odd Fibonacci numbers available to be used for vertex labeling. Out of a total of \(12q+8\) blocks, \(10q+7\) are of Type I, and \(2q+1\) are of Type II. This leads to \(v_f(0)=16q+10\) and \(v_f(1)=32q+22\) , both satisfying the intended limits. As per the assignment, \(3q+2\) even and \(3q+2\) odd nodes on both the columns of the bipartite graph. As a result, we have \(e_f(0) = e_f(1) =18q^{2}+60q+32\) which satisfies the condition \(\vert e_f(0)-e_f(1)\vert \le 1\) as required.
Case 6.Let \(n \equiv 5~(\bmod \ 6)\) then \(n =6q+5\) for some \(q \in \mathbb{N}\) .
Then \(|V(K_{n,n} \odot K_3)|=48q+40\) and \(|E(K_{n,n} \odot K_3)|=36q^{2}+132q+85\) . So, there are \(16q+14\) many even and \(32q+27\) many odd Fibonacci numbers available to be used for vertex labeling. Out of a total of \(12q+10\) blocks, \(10q+8\) are of Type I, and \(2q+2\) are of Type II.This leads to \(v_f(0)=16q+14\) and \(v_f(1)=32q+26\) . Observe that both these values are within the intended limits.
There are \(3q+3\) even and \(3q+2\) odd nodes on the left column and \(3q+3\) odd and \(3q+2\) even nodes on the right column of the bipartite graph. As a result, we have \(e_f(0)=18q^{2}+66q+42\) and \(e_f(1)=18q^{2}+66q+43\) which fulfills the condition \(\vert e_f(0)-e_f(1)\vert \le 1\) as stipulated.
◻
Example 4.5. We provide an explicit Fibonacci cordial labeling for \(K_{2,2} \odot K_3\) using the label set \(\{F_0, \dots, F_{16}\}\) . By Lemma 1.3, we utilize the 6 available even labels \(\{F_0, F_3, F_6, F_9, F_{12}, F_{15}\}\) . The 16 vertices are labeled using the triple-index notation \(v_{i,j,k}\) as follows:
Roots (Inner \(K_{2,2}\) , \(k=0\) ): \(f(v_{1,1,0})=F_0\) , \(f(v_{1,2,0})=F_4\) , \(f(v_{2,1,0})=F_{12}\) , \(f(v_{2,2,0})=F_{10}\) .
Outer nodes for \(i=1\) ( \(k \in \{1,2,3\}\) ): Level \(j=1\) : \(F_3\) , \(F_1, F_2\) . Level \(j=2\) : \(F_6, F_9\) , \(F_5\) .
Outer nodes for \(i=2\) ( \(k \in \{1,2,3\}\) ): Level \(j=1\) : \(F_{15}\) , \(F_7, F_8\) . Level \(j=2\) : \(F_{11}, F_{13}, F_{14}\) .
(The labels \(F_{16}\) remain unassigned.) The internal block edges generate \(\sum e_{K_4}(1) = 4+4+4+0 = 12\) and \(\sum e_{K_4}(0) = 2+2+2+6 = 12\) . The \(K_{2,2}\) , with root parities \(\{E,O\}\) for both partite sets ( \(i=1\) and \(i=2\) ), induces \(e_{K_{2,2}}(1)=2\) and \(e_{K_{2,2}}(0)=2\) . Thus, the total counts are \(e_f(1)=14\) and \(e_f(0)=14\) , yielding \(|e_f(0) – e_f(1)| = 0\) , which satisfies Fibonacci cordiality.
We close this section with the following result, which examines the corona product of \(K_{n,n}\) and \(K_p\) for sufficiently large values of \(p\) . The theorem establishes a condition under which this graph fails to be Fibonacci cordial.
Theorem 4.6. The graph \(K_{n,n} \odot K_{p-1}\) is not Fibonacci cordial when \[p > \frac{3\big(3n + 2 + \sqrt{4n^3 + 9n^2 + 8n + 4}\big)}{2n}.\]
Proof. By Lemma 2.6, if \(K_{n,n} \odot K_{p-1}\) is Fibonacci cordial, then the total number of odd-labeled edges within its \(2n\) block copies of \(K_{p}\) cannot exceed \[\left( \frac{4np^2}{9} + \frac{p}{3} – 1 \right).\]
Additionally, the total number of odd-labeled edges within the inner bipartite graph \(K_{n,n}\) is at most \(n^2\) . On the other hand, the total number of edges in \(K_{n,n} \odot K_{p-1}\) is \[\frac{2n \cdot p(p-1)}{2} + n^2 = np(p-1) + n^2.\]
Therefore, it can not be Fibonacci Cordial if: \[np(p-1) + n^2 – 2\left( \frac{4np^2}{9} + \frac{p}{3} – 1 + n^2 \right) > 1.\]
Solving this inequality gives the bound on \(p\) : \[p > \frac{3\big(3n + 2 + \sqrt{4n^3 + 9n^2 + 8n + 4}\big)}{2n}.\]
Hence, under this condition, \(K_{n,n} \odot K_{p-1}\) cannot be Fibonacci cordial. ◻
In this research, we investigated the Fibonacci cordiality of specific corona graph families, namely \(C_n \odot K_p\) for \(p \in \{4, 5, 6\}\) . This work provides a foundational analysis of how Fibonacci cordiality behaves within corona structures. By extending our study to larger values of \(p\) , we established exact mathematical conditions under which the Fibonacci cordiality of \(C_n \odot K_p\) fails as the order of the corona increases.
Furthermore, we explored the corona family of symmetric bipartite graphs and complete graphs, denoted as \(K_{n,n} \odot K_p\) for \(p \in \{1, 2, 3\}\) . This investigation broadens the understanding of Fibonacci cordiality across diverse graph classes. By deriving specific bounds for cases where \(n\) and \(p\) are sufficiently large, we have highlighted the limitations of cordiality in increasingly complex graph structures. These findings provide a framework for future explorations into more generalized graph products and structural labeling constraints.