A Study of Fibonacci Cordial Labeling in Structured Graph Families
Sarbari Mitra, Soumya Bhoumik · 2025
Read A Study of Fibonacci Cordial Labeling in Structured Graph Families by Sarbari Mitra, Soumya Bhoumik (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-01823.txt.
Introduction
Sarbari Mitra and Soumya Bhoumik study graph labelings that use Fibonacci numbers under a balance rule. In such a labeling, each point of a graph gets a distinct Fibonacci number, the famed sequence where each term sums the prior two. Each edge then takes the parity, even or odd status, of the sum of its end labels. The labeling is cordial when edges split almost evenly between the two parities.
The pair probe which structured graph families admit such labelings. Families include generalized Petersen graphs, helm graphs in open and closed forms, joint sum graphs, and small circulant graphs. New results and concrete examples fill out each family. The work adds to a growing line of labeling studies tied to number sequences.
Catalog record
| CREATOR | Sarbari Mitra, Soumya Bhoumik |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 35 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-01823
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Study of Fibonacci Cordial Labeling in Structured Graph Families Sarbari Mitra, Soumya Bhoumik Abstract A Fibonacci cordial labeling of a graph G G is an injective function f : V ( G ) → { F 0 , F 1 , … , F n } f:V(G)\rightarrow\{F_{0},F_{1},\dots,F_{n}\} , where F i F_{i} denotes the i th i^{\text{th}} Fibonacci number, such that the induced edge labeling f ∗ : E ( G ) → { 0 , 1 } f^{*}:E(G)\rightarrow\{0,1\} , given by f ∗ ( u v ) = ( f ( u ) + f ( v ) ) f^{*}(uv)=(f(u)+f(v)) ( mod 2 ) (\bmod\ 2) , satisfies the balance condition | e f ( 0 ) − e f ( 1 ) | ≤ 1 |e_{f}(0)-e_{f}(1)|\leq 1 . Here, e f ( 0 ) e_{f}(0) and e f ( 1 ) 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. Keywords. Fibonacci Cordial, Helm, Generalized Petersen, Joint sum graph, Circulant graph. 1 Introduction 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 [ 2 ] . 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)=|f(u)-f(v)| satisfies the conditions |n_{0}-n_{1}|\leq 1 , as well as |\varepsilon_{0}-\varepsilon_{1}|\leq 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))\ ({\rm mod\ }2) satisfies the condition |\varepsilon_{0}-\varepsilon_{1}|\leq 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 [ 8 ] , 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 [ 3 ] . Recent contributions to this area can also be found in [ 6 , 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 . 2 Main Results Watkins introduced the generalized Petersen graph (abbreviated as GP) in [ 13 ] . For any integer n\geq 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\leq i\leq n\} and the edge set E=\{u_{i}u_{i+k},\ u_{i}v_{i},\ v_{i}v_{i+1}:1\leq i\leq 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 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\ ({\rm 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\leq i\leq n-p_{2}\\ \displaystyle F_{3(p_{1}+p_{2}+i-n)},&\text{for }n+1-p_{2}\leq i\leq 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\leq i\leq 2p_{1} , set f(v_{i})=F_{3i/2} . For 2p_{1}+1\leq i\leq 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\leq i\leq 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\ ({\rm mod\ }3)\\ \displaystyle F_{n+i+\ell-\lceil\frac{n-i}{2}\rceil},&\text{if }k\equiv 2\ ({\rm mod\ }3)\end{cases} where \ell=\begin{cases}\vskip 3.61371pt\Big\lfloor\frac{3p}{8}\Big\rfloor,&\text{for }k=0,1\\ \vskip 3.61371pt\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 . The total number of edges labeled with 0 and 1 are respectively given by, \varepsilon_{0}=3n-3p_{1}-p_{2},\quad\varepsilon_{1}=3p_{1}+p_{2}, So the difference \tilde{\varepsilon}=|\varepsilon_{0}-\varepsilon_{1}|=|6p_{1}+2p_{2}-3n| satisfies \tilde{\varepsilon}\leq 1 for all p , which can be easily verified. Hence, G is Fibonacci cordial in this case. Case 2. n=3p+1 Assume p\equiv k\ ({\rm 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\leq i\leq n-p_{2}\\ \displaystyle F_{3(p_{1}+p_{2}+i-n)},&\text{for }n+1-p_{2}\leq i\leq 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\leq i\leq 2p_{1} . Now for 2p_{1}+1\leq i\leq 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\leq i\leq 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\ ({\rm mod\ }3)\\ \displaystyle F_{n+i+\ell-\lceil\frac{n-i}{2}\rceil},&\text{if }k\equiv 1\ ({\rm mod\ }3)\end{cases} where \ell=\begin{cases}\vskip 3.61371pt\left\lfloor\frac{3(p+2)}{8}\right\rfloor,&\text{if }k=0\\ \vskip 3.61371pt\left\lfloor\frac{3(p+1)}{8}\right\rfloor,&\text{if }k=1\\ \vskip 3.61371pt\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\ ({\rm 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\leq i\leq n-p_{2}\\ \displaystyle F_{3(p_{1}+p_{2}+i-n)},&\text{for }n+1-p_{2}\leq i\leq 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\leq i\leq 2p_{1} . Now for 2p_{1}+1\leq i\leq n ,