Dynamic Coprime Labeling: A Novel Framework for Time-Sensitive Networks
Anushka Tonapi and Dana Paquin · 2026
Read Dynamic Coprime Labeling: A Novel Framework for Time-Sensitive Networks by Anushka Tonapi and Dana Paquin (2026) 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-2603-22552.txt.
Introduction
Tonapi and Paquin ask whether a network's node labels can stay coprime along every edge while the network changes over time. They define dynamic coprime labeling as a chain of one-to-one labelings driven by a fixed rule that preserves coprimality. Their main result is an equivalence: a graph has such a dynamic labeling exactly when it has a classical coprime labeling. They describe families of allowed rules and build labelings for paths, wheels, cycles, and hypercubes. An application to Carmichael's theorem closes the work.
Catalog record
| CREATOR | Anushka Tonapi and Dana Paquin |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 23516 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.22552
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Dynamic Coprime Labeling: A Novel Framework for Time-Sensitive Networks Anushka Tonapi and Dana Paquin Abstract . In this paper, we introduce dynamic coprime labeling (DCL), a novel extension of coprime labeling for time-sensitive networks. In particular, we explore the question of whether there exists a graph labeling scheme that maintains relative coprimality among adjacent vertices as the graph evolves over time. We modify the definition of coprime labeling for DCL to include an injective coprime labeling function f f , a time variable t t , and a transformation function g g . A DCL on a finite simple graph G G is a sequence ( f t ) t ≥ 0 (f_{t})_{t\geq 0} of injective vertex labelings with the property that every edge remains labeled by coprime integers at every time step, and the evolution is a coprime-preserving transformation g : ℕ → ℕ g:\mathbb{N}\to\mathbb{N} independent of t t . We prove that a graph admits a DCL if and only if it admits a classical coprime labeling (existence equivalence). We characterize families of coprime-preserving transformations and provide proofs of the existence of DCLs for paths, wheels, cycles, and the n n –hypercube. We also include two different types of maps for the coprime-preserving transformation, and look at an application of DCL to Carmichael’s theorem. The results consolidate DCL as a rigorous framework for further algorithmic and applied investigations. 1. Introduction Graph labeling is an area of study within combinatorics and graph theory, having extensive applications in fields such as cryptography and network theory. In general, a graph labeling is an assignment of integers to the vertices or edges, or both, depending on certain constraints. Typically, a graph labeling is an injective function that maps elements from \mathbb{Z} to the vertices or edges of a graph. This field of study goes back to around the 1960s. In the last six decades, over 350 graph labeling techniques have been introduced [ 1 ] . However, most of these labelings have adhered to static conditions only; i.e., they operate in systems that do not change dynamically with time. Wherever graphs are used today, they are usually seen in time-sensitive systems like cryptographic networks or communication systems that are subject to change with time. This motivates the question of whether one can introduce a time parameter into classical labeling schemes while preserving their number-theoretic properties. The coprime labeling of a graph gives adjacent vertices relatively prime integer labels, studied since the work of Entringer and surveyed comprehensively by Gallian [ 1 ] . Prime and coprime labelings have been established for many families of graphs and remain open for others. This paper develops a dynamic extension, dynamic coprime labeling , which aims to preserve classical coprime labeling while allowing labels to evolve through time under a fixed map g . The concept of prime labeling was first introduced by Roger Entringer and was further discussed in a seminal paper by Tout, Dabboucy, and Howalla [ 8 ] . The idea of neighbourhood prime labeling was introduced by Patel and Shrimali [ 5 ] . The neighbourhood of a vertex can be defined as the set of all vertices adjacent to that vertex, excluding itself. If the vertices of a graph G can be labeled with \{1,2,\ldots,n\} so that for any vertex of degree at least 2 , the labels in its neighbourhood are relatively prime, this is called a neighbourhood prime labeling , and a graph that admits such a labeling is called a neighbourhood-prime graph . Neighbourhood prime labeling provides one route to incorporating local number-theoretic structure into graphs. Our focus here is different: we keep the classical edge-based coprimality condition, but allow vertex labels to change systematically over time via a coprime-preserving transformation. 2. Preliminaries: Classical Prime and Coprime Labelings We use \mathbb{N}=\{1,2,3,\dots\} , \gcd(\cdot,\cdot) for the greatest common divisor, and finite simple graphs G=(V,E) . Definition 2.1 (Prime labeling) . For |V|=n , a prime labeling is a bijection f:V\to\{1,2,\dots,n\} such that \gcd(f(u),f(v))=1 for all uv\in E [ 1 ] . Definition 2.2 (Coprime labeling) . A coprime labeling assigns pairwise distinct values in \{1,\dots,k\} (with k\geq n ) to V so that \gcd(f(u),f(v))=1 for all uv\in E [ 2 ] . 1 2 3 4 Figure 1. A prime-labeled path P_{4} (labels 1,2,3,4 satisfy \gcd(i,i+1)=1 ). 3. Definitions and Notation We collect the definitions used throughout. Definition 3.1 (Coprime-preserving transformation) . A map g:\mathbb{N}\to\mathbb{N} is coprime-preserving if \gcd(a,b)=1\ \Longrightarrow\ \gcd\bigl(g(a),g(b)\bigr)=1\quad\text{for all }a,b\in\mathbb{N}. Definition 3.2 (Dynamic coprime labeling (DCL)) . Let G=(V,E) be a finite simple graph. A dynamic coprime labeling (DCL) of G with respect to a coprime-preserving map g:\mathbb{N}\to\mathbb{N} is a sequence of injective labelings f_{t}:V\to\mathbb{N}\quad(t\geq 0) such that: (1) f_{0} is a coprime labeling of G (i.e. \gcd(f_{0}(u),f_{0}(v))=1 for all uv\in E ), (2) f_{t+1}=g\circ f_{t} for all t\geq 0 , and (3) for every edge uv\in E and every time t\geq 0 , \gcd(f_{t}(u),f_{t}(v))=1. We say that G admits a DCL (for a given g ) if such a sequence exists. Definition 3.3 (Periodic DCL) . A DCL (f_{t})_{t\geq 0} is periodic if there exists T\geq 1 with f_{t+T}=f_{t} for all t\geq 0 ; equivalently, the label set \mathcal{L}=\bigcup_{t\geq 0}f_{t}(V) is finite and g acts as a permutation on \mathcal{L} . Definition 3.4 ( n –hypercube graph) . The n –hypercube Q_{n} is defined on the vertex set V(Q_{n})=\{0,1\}^{n} where two vertices are adjacent if and only if they differ in exactly one coordinate. It is bipartite with parts V_{0}=\{x\in\{0,1\}^{n}:\sum_{i}x_{i}\text{ even}\},\quad V_{1}=\{x\in\{0,1\}^{n}:\sum_{i}x_{i}\text{ odd}\}. Definition 3.5 (Bounded/Unbounded Labelings) . Let (f_{t})_{t\geq 0} be a dynamic coprime labeling (DCL) of a finite graph G=(V,E) with respect to g . Define the label–evolution set \mathcal{L}\;:=\;\bigcup_{t\geq 0}f_{t}(V)\;=\;\{\,x\in\mathbb{N}\;:\;\exists\,t\geq 0,\ \exists\,v\in V\text{ with }x=f_{t}(v)\,\}. We say the DCL is bounded if \mathcal{L} is finite, and unbounded otherwise. We present two schemes: (1) Periodic/bounded case. If there exists a finite set S\subset\mathbb{N} with f_{0}(V)\subseteq S and g(S)=S such that g is a permutation on S , then f_{t+T}=f_{t} for some T\geq 1 (hence the DCL is periodic and \mathcal{L}\subseteq S is finite). (2) Unbounded case. If g is injective and does not act as a permutation on any finite set containing f_{0}(V) , then the sequence of label sets \{f_{t}(V)\}_{t\geq 0} introduces infinitely many distinct values; equivalently, \mathcal{L} is infinite (labels grow without bound). Remark 3.6 . We outline a framework for establishing DCL results. (1) Verify that g is coprime-preserving. Examples include g(x)=x^{k} for integers k\geq 1 and the map g(x)=p_{x} sending x to the x -th prime. In contrast, additive shifts x\mapsto x+c are not coprime-preserving in general. (2) Induction over time. If f_{t} is coprime on edges and g is coprime-preserving, then f_{t+1}=g\circ f_{t} is coprime on edges by induction. If g is injective, injectivity of the labeling is also preserved. (3) Periodicity versus growth. If g acts as a permutation on a finite label set S containing f_{0}(V) , then (f_{t}) is periodic. If g is injective and unbounded on f_{0}(V) , labels grow without bound. 4. Main Results Theorem 4.1 (Existence Equivalence) . A finite graph G admits a dynamic coprime labeling (with respect to some coprime-preserving map g ) if and only if it admits a