Fact-checked by Grok 2 weeks ago

Graph labeling

In graph theory, graph labeling is the assignment of integers—or occasionally other values—to the vertices, edges, or both of a graph, subject to prescribed conditions that ensure distinctness, consecutiveness, balance, or other structural properties in the resulting labels.^[1] This discipline emerged in the 1960s as a tool for addressing problems in graph decompositions and has since evolved into a prolific area of research, with over 3,000 published papers exploring more than 200 distinct labeling variants.^[1] The foundational developments trace back to Gerhard Ringel's 1963 conjecture on labeling trees to facilitate the cyclic decomposition of complete graphs, followed by Anton Rosa's 1967 introduction of β-valuations, now termed graceful labelings, where vertices receive distinct labels from 0 to n-1 (with n the number of vertices) and edges obtain distinct absolute differences forming the set {1, 2, \dots, m} (with m the number of edges).^[1] Subsequent innovations in the 1970s and 1980s, including contributions from Alexander Kotzig on magic valuations and Robert Graham and Neil Sloane on harmonious labelings (where adjacent vertex sums are distinct modulo the edge count), expanded the field to encompass diverse types such as α-labelings (graceful with a separating boundary label), magic labelings (constant sums of incident labels), antimagic labelings (distinct vertex sums from edge labels), cordial labelings (balanced 0-1 assignments with controlled edge differences), and radio labelings (ensuring minimum label separations to model frequency assignments).^[1] These labelings often target specific graph classes like trees, cycles, paths, and bipartite graphs, with open conjectures—such as the graceful labeling conjecture for all trees—driving ongoing investigations.^[1] Graph labelings find applications in coding theory for error-correcting codes, network design for optimal routing and channel allocation, communication systems for frequency assignment, cryptology for secure encoding, x-ray crystallography for molecular structure analysis, circuit design in VLSI for wire routing, and combinatorial optimization for resource allocation and fault detection.^[1] The field's interdisciplinary reach underscores its utility in modeling real-world constraints where distinct identifiers or balanced distributions are essential, while surveys continue to catalog results, properties, and unresolved problems across these domains.^[1]

Fundamentals

Definition and scope

In graph theory, a graph labeling is an assignment of labels, typically non-negative integers, to the vertices, edges, or both of a graph G = (V, E), subject to certain conditions such as injectivity, distinct sums or differences of labels on adjacent elements, or constant weights of specified combinations. These conditions ensure that the labeling satisfies predefined structural or numerical constraints, distinguishing it from arbitrary assignments. Graph labelings are studied for their combinatorial properties and utility in modeling discrete structures. The scope of graph labeling encompasses vertex labelings, where labels are assigned solely to vertices in V; edge labelings, where labels are assigned solely to edges in E; and total labelings, where labels are assigned to the union V \cup E. Labelings may be bijective or injective, requiring one-to-one mappings from the labeled elements to a set of distinct integers, or they may employ modular arithmetic, where labels are considered modulo some integer q to wrap around a finite range. This breadth allows labelings to address diverse problems in graph theory, from embedding graphs into integer grids to optimizing network representations.^[1] Motivations for studying graph labelings stem from their role in solving graph decomposition problems, such as Ringel's conjecture, which was proved in 2021, and posits that the complete graph K_{2n+1} can be decomposed into $2n+1 edge-disjoint isomorphic copies of any tree with n edges—a challenge where labelings provide constructive proofs by mapping edges to distinct differences. Additionally, labelings find applications in coding theory, where they facilitate the design of error-correcting codes by encoding graph structures into label sequences that detect or correct transmission errors in communication networks.^[1] Key general properties of graph labelings include the span, defined as the difference between the maximum and minimum labels used, which measures the "width" of the label set and often relates to the graph's size or density. The bandwidth of a graph is the minimum, over all bijections f: V \to \{1, 2, \dots, |V|\}, of the maximum absolute difference |f(u) - f(v)| between labels of adjacent vertices, influencing applications like graph layout and VLSI design by quantifying how compactly a graph can be represented linearly. For instance, the path graph P_3 admits a labeling with vertices 1, 2, 3, yielding adjacent differences of 1, illustrating bandwidth 1. Graceful labeling serves as a classic example of a vertex-to-edge induced labeling.^[1]

Classification by labeling domain

Graph labelings are broadly classified based on the domain to which labels are assigned: vertices, edges, or both vertices and edges combined. This classification highlights fundamental differences in the structure and constraints of each type, influencing the properties that must be satisfied, such as distinctness or specific arithmetic patterns induced on the unlabeled elements. Vertex labelings focus on assigning numbers to vertices and deriving conditions from the edges, edge labelings assign to edges and impose vertex-based constraints, while total labelings integrate both for more stringent global conditions.^[1] In vertex labelings, integers are assigned to the vertices of a graph G=(V,E), typically via a function f: V \to \mathbb{N}_0 (non-negative integers), such that the induced labels on edges—often defined as |f(u) - f(v)| or f(u) + f(v) for an edge uv \in E—satisfy particular conditions, such as being distinct or forming a consecutive set. For instance, a graceful labeling is a bijective vertex labeling f: V \to \{0,1,\dots,|E|\} that induces distinct edge differences \{1,2,\dots,|E|\}, ensuring a structured bijection between vertex and edge properties. These labelings emphasize how vertex assignments propagate constraints to edges, often requiring injectivity on vertices to avoid overlaps in induced values, and are common in studies of trees and cycles where edge distinctness models bandwidth or embedding problems.^[1] Edge labelings, in contrast, directly assign integers to the edges via g: E \to \mathbb{N}, with conditions typically imposed on the vertices through sums or other aggregates of incident edge labels. A common requirement is that the sums \sum_{e \ni v} g(e) over edges e incident to each vertex v are distinct, as in antimagic labelings where edges receive \{1,2,\dots,|E|\} and vertex sums differ. Another example is edge-magic labelings, where distinct positive integer edge labels yield a constant vertex sum, reversing the induction direction from vertex labelings by prioritizing edge assignments while constraining vertex aggregates. This approach often highlights degree-related distinctions, with higher-degree vertices accumulating larger sums under bijective edge labels.^[1] Total labelings extend this framework by assigning labels to both vertices and edges simultaneously, usually through a bijective function h: V \cup E \to \{1,2,\dots,|V|+|E|\}, where conditions apply to combined elements, such as the edge weight h(u) + h(uv) + h(v) being constant for every edge uv. Edge-magic total labelings exemplify this, requiring all such weights to equal a fixed integer k, which imposes balanced distribution across the graph. Variants like super edge-magic total labelings further restrict low labels to vertices and high ones to edges, distinguishing them from regular total labelings by emphasizing degree influences—low labels on high-degree vertices to maintain constancy. Total labelings thus combine the inductive strengths of vertex and edge types, yielding stronger constraints that test global harmony but are harder to achieve, often limited to specific graph classes like paths or complete bipartites.^[1] The key differences among these domains lie in their directional constraints and complexity: vertex labelings induce edge properties from vertex choices, promoting sparsity in vertex labels to ensure edge variety; edge labelings induce vertex properties from edge choices, often leveraging edge bijections for vertex discrimination; and total labelings unify both, demanding coordination that amplifies challenges, such as avoiding label conflicts across the entire graph. This classification underpins much of graph labeling theory, guiding the selection of appropriate types for conjectures and applications.^[1]

Historical development

Origins in the 1960s

The origins of graph labeling trace back to efforts in the early 1960s to address problems in graph decompositions and combinatorial designs, particularly motivated by Gerhard Ringel's 1963 conjecture on the decomposition of complete graphs into isomorphic copies of trees. Ringel's problem, rooted in map coloring and the efficient packing of graphs, required labelings that would ensure edge-disjoint subgraphs with specific structural properties, laying the groundwork for labeling techniques that could verify such decompositions. In response, Alexander Rosa introduced β-valuations in 1967 as a method to label vertices of a graph with distinct nonnegative integers such that the absolute differences on edges form a consecutive set of integers, directly aiding the decomposition of complete graphs K_{2m+1} into m+1 isomorphic subgraphs for trees with m edges.^[1]^[2] A pivotal early contribution came from Jiří Sedláček in 1963, who proposed the concept of magic labelings for graphs, where edges are assigned distinct real numbers such that the sum of labels incident to each vertex is constant, extending magic square ideas to graph theory and influencing subsequent sum-based labeling variants.^[1] Concurrently, Solomon Golomb explored difference labelings in 1972, focusing on trees and assigning vertex labels from 0 to m (for m edges) so that edge differences are distinct integers from 1 to m, which he later termed "graceful" and recognized as equivalent to Rosa's β-valuations for certain graphs. These works established the foundational framework for injective vertex labelings tied to edge differences, emphasizing bijective mappings that preserve structural integrity. Rosa's 1967 paper provided the first systematic classification, demonstrating that β-valuations are equivalent to what would become known as graceful labelings, and proved initial results such as the existence of such labelings for paths and even cycles, while noting challenges for odd cycles. These proofs highlighted the potential for broader applications in decomposition problems, sowing the seeds for the graceful tree conjecture without formally stating it at the time, and marking the 1967 publication as a cornerstone that unified disparate labeling ideas into a coherent research area.^[2]

Key advancements from 1970s to present

In the 1970s, graph labeling saw foundational advancements in graceful labelings, with Anton Kotzig and Alexander Rosa demonstrating that specific classes of trees, such as rooted symmetric trees, admit graceful labelings, building on Rosa's earlier β-valuations.^[3] Their work established proofs for caterpillars and other tree subclasses, fueling interest in the graceful tree conjecture.^[1] This period also introduced variants like α-labeling for bipartite graphs, where labels are assigned to ensure induced edge labels form a permutation of 1 to the number of edges, with Rosa providing early constructions for complete bipartite graphs.^[4] The 1980s marked a surge in new labeling types, including Ronald Graham and Neil Sloane's introduction of harmonious labeling in 1980, which assigns distinct vertex labels modulo the number of edges such that induced edge sums are also distinct, with applications to additive bases.^[5] Ismail Cahit proposed cordial labeling in 1987, a binary variant balancing the counts of 0- and 1-labeled vertices and edges differing by at most one.^[1] Roger Entringer's prime labeling, emerging around 1980, assigns distinct positive integers to vertices such that adjacent vertices receive coprime labels, with conjectures that all trees admit such labelings.^[6] Edge-graceful labelings, defined by S.P. Lo in 1985 (though early explorations trace to Bloom's 1979 work on related valuations), extended graceful concepts to edge-induced differences.^[1] From the 1990s to the 2000s, the field exploded with over 1,000 papers, focusing on antimagic labelings introduced by Nora Hartsfield and Gerhard Ringel in 1990, where vertex labels induce distinct edge sums.^[1] Magic total labelings, advanced by James MacDougall in the 1990s, assign consecutive integers to vertices and edges such that each vertex's incident labels sum to a constant, with extensions to super edge-magic totals by Hiroshi Enomoto et al. in 1998.^[1] Joseph Gallian's dynamic surveys, beginning in 1989 and updated through 2022, cataloged this growth, documenting over 200 labeling techniques across more than 3,000 papers by 2022, emphasizing computational verifications for small graphs.^[1] In the 2010s to the present, major breakthroughs included proofs of Ringel's conjecture on decomposing complete graphs into isomorphic spanning trees, achieved independently by Peter Keevash and Robert Staden in 2020 using quasirandom graph decompositions, and by Richard Montgomery, Alexey Pokrovskiy, and Benny Sudakov in 2021 via probabilistic methods.^[7] Edinah K. Gnang claimed a proof of the graceful tree conjecture in 2022, asserting all trees admit graceful labelings, though it remains unverified; as of November 2025, the conjecture is still open, with Gnang's claims and subsequent 2024 preprints unaccepted by the community.^[8]^[9] Recent work incorporates computational tools for verifying labelings on larger graphs, with Gallian's surveys highlighting persistent open problems like the graceful tree conjecture.^[1]

Graceful labelings and variants

Graceful labeling

A graceful labeling of a simple connected graph G with q edges is a bijection f: V(G) \to \{0, 1, \dots, q\} such that the induced edge labels |f(u) - f(v)| for each edge uv \in E(G) form the set \{1, 2, \dots, q\}. This labeling was introduced by Alexander Rosa in 1967 as a \beta-valuation to address problems in graph decompositions, where the span of the labeling equals the number of edges, ensuring all positive integers up to q appear exactly once as edge differences. The concept gained prominence through connections to Ringel's conjecture on decomposing complete graphs into trees, with Solomon Golomb popularizing the term "graceful" in 1972. The Graceful Tree Conjecture (GTC), proposed by Rosa in 1967 and independently by Ringel and Kotzig, states that every tree admits a graceful labeling; this remains an open problem despite extensive verification. All trees of order up to 35 have been computationally verified to be graceful, and specific classes such as paths P_n for all n, stars K_{1,n} for all n, caterpillars, and trees with diameter at most 5 or at most 4 endpoints are known to be graceful. For cycles, C_n is graceful if and only if n \equiv 0 \pmod{4} or n \equiv 3 \pmod{4}, as proven by Rosa for odd n and extended to multiples of 4 by subsequent work. Complete bipartite graphs K_{m,n} (with m, n > 1) are graceful, with explicit constructions provided for cases like K_{2,n} when n is odd. Unicyclic graphs, which contain exactly one cycle, are mostly graceful under the Truszczyński conjecture from 1984, which posits that all such graphs are graceful except for cycles C_n with n \equiv 1 \pmod{4} or n \equiv 2 \pmod{4}; this remains open, though classes like dragons and unicyclic graphs with a triangle are confirmed graceful. Bermond's 1979 conjecture asserts that all lobsters—trees obtained by attaching paths of length at most 2 to a path backbone—are graceful; partial progress includes proofs for lobsters with perfect matchings and certain symmetric cases, but the full conjecture is unresolved. For example, consider the path P_3 with vertices a-b-c; the labeling f(a) = 0, f(b) = 2, f(c) = 1 induces edge labels |0-2| = 2 and |2-1| = 1, covering \{1, 2\} distinctly. For a graceful cycle like C_4, one construction labels vertices around the cycle as 0, 4, 1, 3, yielding edge differences 4, 3, 2, 1. Graceful labelings are dual to edge-graceful labelings, where edges are labeled to induce distinct vertex differences from 1 to q.

Edge-graceful and odd-graceful labelings

An edge-graceful labeling of a graph G with n vertices and q edges is a bijection g: E(G) \to \{1, 2, \dots, q\} such that the induced vertex labels, defined as the sum of the labels of the edges incident to each vertex modulo n, form the distinct values \{0, 1, \dots, n-1\}. This approach is the dual of the standard graceful labeling, where vertices are labeled instead of edges, but with analogous conditions on induced differences. The concept was introduced as a variation to explore similar bijective properties in the opposite direction, with early work by Rosa examining its application to trees and cycles. It has been conjectured that every tree of odd order admits an edge-graceful labeling, a result attributed to Lee, though this remains open despite verification for trees up to certain sizes and specific subclasses. For instance, all paths are edge-graceful, and certain trees such as caterpillars and those with diameter at most 5 have been proven to satisfy the condition. A necessary condition for a graph to be edge-graceful is q(q+1) \equiv n(n-1)/2 \pmod{n}. An odd-graceful labeling of a graph G with q edges is an injection f: V(G) \to \{0, 1, \dots, 2q-1\} such that the induced edge labels |f(u) - f(v)| for each edge uv are the distinct odd integers \{1, 3, \dots, 2q-1\}. This labeling is equivalent to a graceful labeling when restricted to bipartite graphs, as the odd differences complement the even differences in the graceful case. Proposed by Gnanajothi, it extends graceful concepts by enforcing oddness in the differences, with a conjecture that all trees are odd-graceful, supported by proofs for trees of order up to 10 and various subclasses. Key results include that all paths are odd-graceful, while cycles C_n admit an odd-graceful labeling if and only if n is even. For example, the path P_2 can be odd-gracefully labeled with vertices 0 and 3, yielding the edge label |3-0| = 3, the sole odd integer in \{1, 3, \dots, 3\}. Additional classes such as caterpillars, lobsters, and certain bipartite graphs like complete bipartite graphs K_{m,n} with m \leq n have been shown to be odd-graceful.

Harmonious and magic labelings

Harmonious labeling

A harmonious labeling of a graph G with q edges is an injective function f: V(G) \to \{0, 1, \dots, q\} such that the induced edge labels f(u) + f(v) \pmod{q+1} are all distinct for every edge uv \in E(G).^[5] A graph that admits such a labeling is called harmonious. This labeling allows for non-surjective vertex mappings, though when q+1 is prime, certain properties like field operations can facilitate constructions. Unlike graceful labeling, which relies on absolute differences to produce distinct edge labels from 1 to q, harmonious labeling employs modular sums to achieve distinctness modulo q+1.^[5] All paths P_n with n \geq 1 admit harmonious labelings. For example, for P_3 (q=2), label the vertices 0, 1, 2; the edge sums are $0+1 = 1 \pmod{3} and $1+2 = 3 \equiv 0 \pmod{3}, which are distinct. Cycles C_n are harmonious if and only if n is odd, as even cycles fail due to parity constraints on the sums modulo n. Complete bipartite graphs K_{m,n} are harmonious precisely when \min(m,n) = 1, reducing to stars, which are paths or trees.^[5] The Graham-Sloane conjecture posits that every tree is harmonious, a problem originating in 1980 and remaining open despite verification for all trees up to 35 vertices and many subclasses, such as binary trees and caterpillars.^[5] Recent progress as of 2024 confirms the conjecture for trees of bounded degree. A sequential harmonious labeling is a bijective variant where f maps onto \{0, 1, \dots, q\}, coinciding with the standard definition for trees where |V| = q+1.^[5]^[10]

Magic-type labelings

Magic-type labelings are total labelings of a graph where induced sums associated with edges or vertices are constant. These labelings generalize concepts from magic squares to graphs and are distinct from harmonious labelings, which use modular arithmetic on edge-induced vertex sums to ensure distinctness.^[1] An edge-magic total labeling of a graph G with vertex set V of order v = |V| and edge set E of size e = |E| is a bijection h: V \cup E \to \{1, 2, \dots, v+e\} such that h(u) + h(uv) + h(v) = k for some constant k and every edge uv \in E.^[1] The magic constant k is determined by the labeling as k = \frac{ \sum_{i=1}^{v+e} i + \sum_{v \in V} (\deg(v) - 1) h(v) }{e}. A graph admitting such a labeling is called edge-magic total. A stronger variant, super edge-magic total labeling, requires the vertices to receive the labels \{1, 2, \dots, v\} while edges receive \{v+1, v+2, \dots, v+e\}.^[1] A vertex-magic total labeling is a bijection h: V \cup E \to \{1, 2, \dots, v+e\} such that for every vertex v \in V, h(v) + \sum_{vu \in E} h(vu) = k, where the sum is over edges incident to v.^[1] The super vertex-magic total labeling analogously assigns \{1, 2, \dots, v\} to vertices. For regular graphs, edge-magic total and vertex-magic total labelings are equivalent, as the constant sums align due to uniform degrees.^[1] Key results include that cycles C_n admit edge-magic total labelings for all n \geq 3, with super edge-magic total labelings existing precisely when n is odd.^[1] Complete graphs K_n are edge-magic total if and only if n = 1, 2, 3, 5, or $6.^[1] Paths P_n are super edge-magic total for all n \geq 1.^[1] For C_3 \cong K_3, an edge-magic total labeling assigns labels 1, 2, 3 to the vertices and 6, 5, 4 to the edges (with the edge between vertices labeled 1 and 2 receiving 6, between 1 and 3 receiving 5, and between 2 and 3 receiving 4), yielding constant sum k=9 for each edge.^[11] MacDougall's conjecture posits that every regular graph of order at least 3, except K_2 and $2K_3, admits a vertex-magic total labeling; this has been verified for all regular graphs of odd order up to 29, all cubic graphs except the Petersen graph, and various other families, but remains open in general.^[1]

Other prominent labelings

Cordial and product cordial labelings

A cordial labeling of a graph G = (V, E) is a function f: V \to \{0, 1\} such that the induced edge labeling f^*(uv) = |f(u) - f(v)| assigns to each edge a label in \{0, 1\}, the number of vertices labeled 0 and the number labeled 1 differ by at most 1 (i.e., |v_f(0) - v_f(1)| \leq 1), and the number of edges labeled 0 and the number labeled 1 differ by at most 1 (i.e., |e_f(0) - e_f(1)| \leq 1). A graph admitting such a labeling is called cordial. This labeling measures a balance in the distribution of binary labels across vertices and the resulting edge differences, serving as a weaker variant of graceful and harmonious labelings.^[12] Key results establish cordiality for broad classes of graphs. All trees are cordial, as they can be labeled to satisfy the balance conditions through recursive construction from smaller subtrees.^[12] All cycles C_n (for n \geq 3) are cordial; for even n, adjacent pairs of equal labels achieve the required parity balance.^[12] All bipartite graphs are cordial, leveraging the bipartition to assign labels that equalize counts within parts.^[12] However, the complete graph K_n is cordial if and only if n \leq 3, as larger n leads to imbalances in edge label counts exceeding the threshold.^[12] For example, the cycle C_4 admits a cordial labeling by assigning 0 to two adjacent vertices and 1 to the other two adjacent vertices. This yields v_f(0) = 2, v_f(1) = 2, two edges with label 0 (the same-label edges), and two with label 1 (the differing-label edges), satisfying |e_f(0) - e_f(1)| = 0 \leq 1.^[12] A product cordial labeling is defined analogously: f: V \to \{0, 1\} induces edge labels f^*(uv) = f(u) f(v) \in \{0, 1\} (1 only if both endpoints are 1, else 0), with the same balance conditions on vertex and edge label counts. A graph is product cordial if it admits such a labeling. This variant emphasizes balance in the presence of "both-1" edges, relating to binary representations of graph structure.^[13]

Prime and antimagic labelings

A prime labeling of a graph G with vertex set V(G) of order n is a bijection f: V(G) \to \{1, 2, \dots, n\} such that for every edge uv \in E(G), \gcd(f(u), f(v)) = 1. A graph admitting such a labeling is called prime. The concept originated with Roger Entringer in the early 1980s and was formally introduced by Tout, Dabboucy, and Howalla, who proved that all trees with a prime number of vertices admit prime labelings. Entringer conjectured that every tree is prime, a claim that remains open as of 2025 despite partial progress. Notably, Haxell, Pikhurko, and Taraz established that all sufficiently large trees are prime, confirming the conjecture asymptotically.^[1] For complete graphs K_n, prime labelings exist precisely when n \leq 3, as larger cliques require labeling adjacent vertices with coprime numbers from \{1, 2, \dots, n\}, which becomes impossible due to the density of composites and shared factors among small integers.^[14] An antimagic labeling of a graph G with edge set E(G) of size m is a bijection g: E(G) \to \{1, 2, \dots, m\} such that the vertex weights w_g(v) = \sum_{e \ni v} g(e) are distinct for all vertices v \in V(G). A graph admitting such a labeling is antimagic. Hartsfield and Ringel introduced this in 1990, conjecturing that every connected graph except the path P_2 (isomorphic to K_2) is antimagic; they specifically highlighted trees other than P_2 and verified it for paths, cycles, complete graphs, and wheels.^[15] The conjecture holds for trees with at most one vertex of degree 2, as proven by Kaplan, Lev, and Roditty. For graphs with large maximum degree, Yilma showed that any graph on n vertices with maximum degree at least n - 3 is antimagic.^[16] A generalization is the (a, d)-antimagic labeling, where the distinct vertex weights form an arithmetic progression starting at a with common difference d > 0; the standard antimagic labeling corresponds to d=1. This variant has been studied for various graph classes, including paths and cycles, which admit such labelings for appropriate a and d. For example, consider the path P_3 with vertices u, v, w and edges e_1 = uv, e_2 = vw. Labeling g(e_1) = 1, g(e_2) = 2 yields weights w_g(u) = 1, w_g(v) = 3, w_g(w) = 2, all distinct.^[15] In contrast to magic labelings, where vertex weights are uniform, prime and antimagic labelings emphasize number-theoretic distinctions like coprimality or unique sums.

Applications and open problems

Practical applications

Graph labelings have found applications in coding theory, where graceful and harmonious labelings model error-correcting codes and sequence designs, such as those used in radar signal processing through difference sets that ensure distinct differences for reliable detection.^[17]^[18] In cryptography, magic labelings contribute to key distribution protocols by providing structured assignments that enhance encryption schemes.^[19]^[20] Antimagic labelings are employed in wireless networks for frequency assignment, ensuring distinct sums for adjacent vertices to minimize interference in channel allocation.^[21]^[22] Similarly, radio labelings address channel allocation by assigning labels such that the span satisfies the condition where the difference in labels plus the graph distance is at least the diameter plus one, optimizing bandwidth in communication networks.^[23] In x-ray crystallography, graceful labelings model diffraction patterns by representing interatomic distances in crystal lattices, aiding in the determination of atomic positions through the induced edge labels.^[24] Cordial labelings assist in database management for query optimization, where balanced label counts facilitate efficient indexing and retrieval structures.^[17] Harmonious labelings generate sequences applicable in astronomy and radar systems, modeling periodic signals with unique sum properties for precise timing and positioning.^[18]

Major conjectures and recent progress

One of the most prominent open problems in graph labeling is the Graceful Tree Conjecture, which posits that every tree admits a graceful labeling.^[25] Proposed independently by Ringel, Kotzig, and Rosa in the 1960s, it remains unresolved despite extensive verification: all trees with up to 35 vertices have been computationally confirmed to be graceful.^[25] In 2022, Edinah Gnang claimed a proof using functional equations and generating functions, but the argument has not been verified by the community and is not widely accepted.^[8]^[26] Another significant conjecture concerns α-labelings, a refinement of graceful labelings for bipartite graphs where vertex labels in one part are at most α and in the other exceed α. The conjecture states that every tree with maximum degree at most 3 admits an α-labeling.^[25] This remains open, though it has been verified computationally for all such trees with fewer than 30 vertices.^[25] Additional open conjectures include the assertion that no tree admits a super vertex-magic total labeling, where labels on vertices and edges form a bijection to {1, ..., |V| + |E|} such that each vertex sum equals a constant.^[25] This has been confirmed for many tree classes, such as paths, stars, and caterpillars, but the general case persists.^[27] In antimagic orientations, where an edge bijection induces distinct vertex sums allowing a vertex-distinguishing orientation, the conjecture holds that every connected graph admits such an orientation; this has been proven for all regular graphs and biregular bipartite graphs.^[28] Recent advancements have resolved longstanding problems related to labeling. In 2021, Ringel's 1963 tree-packing conjecture—that the complete graph K_{2m+1} decomposes into $2m+1 copies of any tree with m edges—was proven using probabilistic methods on quasirandom graphs.^[29] Independently, Montgomery, Pokrovskiy, and Sudakov established it via blow-up lemmas and equitable colorings.^[30] For sum graphs, where edges connect vertices whose labels sum to another label, Rupert Li provided asymptotically tight bounds on the sum-diameter—the minimal span of labels needed for a connected sum labeling—in 2021.^[31] Additionally, in 2021, Gómez and Kovář confirmed super vertex-magic total labelings for complete graphs K_n when n \equiv 0 \pmod{4} and n > 4, resolving a prior conjecture.^[32] The field encompasses over 100 distinct conjectures across labeling types, with many partially resolved through case analyses or computational checks; Joseph Gallian's annual dynamic surveys meticulously track progress and open questions.^[25]

References

[1]
[PDF] A Dynamic Survey of Graph Labeling
In this survey I have collected everything I could find on graph labeling. For the convenience of the reader the survey includes a detailed table of contents ...Missing: review | Show results with:review
[2]
[2202.03178] A proof of the Kotzig-Ringel-Rosa Conjecture - arXiv
Feb 4, 2022 · The Kotzig-Ringel-Rosa conjecture asserts that every tree admits a graceful labeling. We provide a proof of this long standing conjecture.
[3]
[PDF] A Dynamic Survey of Graph Labeling
Graph labelings were first introduced in the mid 1960s. In the intervening years over 200 graph labelings techniques have been studied in over 3000 papers.
[4]
Magic Valuations of Finite Graphs | Canadian Mathematical Bulletin
Nov 20, 2018 · , On certain valuations of the vertices of a graph, Theory of Graphs, Internat. Sympos., ICC Rome 1966, Paris, Dunod (1967), 349-355.Google ...
[5]
https://epubs.siam.org/doi/10.1137/0601045
[6]
New families of graphs that have α-labelings - ScienceDirect
Jun 10, 1997 · We also present some evidence to support the conjecture that every bipartite graph G eventually has an α-labeling. ... Sci., 319 (1979), pp ...
[7]
On Additive Bases and Harmonious Graphs - SIAM.org
A connected graph with n edges is called harmonious if it is possible to label the vertices with distinct numbers (modulo n) in such a way that the edge sums ...
[8]
A comprehensive survey on prime graphs - IOP Science
We call a prime graph if it admits a prime labeling. Around 1980, Roger Entringer conjectured that “all trees have a prime labeling” which is not settled till ...
[9]
https://arxiv.org/abs/2410.13840
[10]
[PDF] A Dynamic Survey of Graph Labeling
A graph labeling is an assignment of integers to the vertices or edges, or both, subject to certain conditions. Graph labelings were first introduced in the ...
[11]
Edge-graceful Labelings
Conjecture 2: (Lee [L2]) A connected graph with n vertices and m edges is edge-graceful if and only if m(m+1)≡n(n-1)/2 (mod n).
[12]
[PDF] Edge-magic total labelings
Sedlacek [17] defined a graph to be magic if it had an edge-labeling, with range the real numbers, such that the sum of the labels around any vertex equalled ...
[13]
Cordial Graphs: A Weaker Version of Graceful and Harmonious ...
Aug 5, 2025 · Cordial Graphs: A Weaker Version of Graceful and Harmonious Graphs. January 1987; Ars Combinatoria 23:201-208. Authors: Ibrahim Cahit at Near ...
[14]
(PDF) EP-cordial labelings of graphs - ResearchGate
An EP-cordial graph is one that admits an EP-cordial labeling. It is shown that every graph is an induced sub graph of an EP-cordial graph. The maximum size ...Missing: conjecture | Show results with:conjecture
[15]
Tout, A., Dabboucy, A.N. and Howalla, K. (1982) Prime Labeling of ...
In the present work we investigate some classes of graphs and disjoint union of some classes of graphs which admit prime labeling.
[16]
[PDF] integers 19 (2019) minimum coprime labelings for operations on ...
Mar 15, 2019 · Complete Graphs and Wheels. Consider the complete graph Kn on n vertices. It is easy to see that Kn is prime if and only if n ≤ 3. The ...
[17]
[PDF] Antimagic labelings In 1990, Hartsfield and Ringel introduced the ...
They conjectured that every connected graph other than K2 is antimagic. An antimagic labeling of a graph G = (V,E) is a bijection from E to the a set of ...
[18]
[PDF] Antimagic Properties of Graphs with Large Maximum Degree
Such a labeling is called antimagic if wτ (v) = wτ (u) for all distinct u,v ∈ V. The graph G is antimagic if it permits an antimagic labeling. It is ...Missing: proven | Show results with:proven
[19]
[PDF] Magic and Antimagic Labeling of Graphs - CORE
If the evaluation forms an arithmetic progression starting at a and with difference d, d a non-negative integer, then the labeling is called an (a, d)-antimagic.
[20]
[PDF] A DYNAMIC SURVEY OF GRAPH LABELING 1. Introduction Most ...
In 1979 Bermond [Be] conjectured that lobsters are graceful (a lobster is a tree with the property that the removal of the endpoints leaves a caterpillar).
[21]
[PDF] Harmonious labeling of graphs
Labelled graphs useful models variety range applications such as: coding theory crystallography, astronomy, contact system, data base managing limit programming ...
[22]
Efficient Graph Network Using Total Magic Labeling and Its ... - MDPI
If the domain is a vertex (or edge) set, the labeling is referred to as vertex (or edge) labeling. When the domain contains both vertices and edges, the ...3. Graph Network... · 4. Encryption System Of... · 4.2. Encryption Algorithm: L...
[23]
(PDF) An application of super mean and magic graphs labeling on ...
Aug 6, 2025 · We will give an application of these labeling to increase the security level of Affine Cipher in which to encrypt a text on socials media.
[24]
Antimagic Labeling of Graphs Using Prime Numbers - arXiv
Mar 16, 2024 · This research paper focuses on antimagic labeling of different types of graphs and trees. It entails the assignment of distinct prime values to edges.
[25]
Anti-k-labeling of graphs - ScienceDirect.com
Dec 15, 2019 · The frequency assignment problem is an important problem that arises in the design of the wireless radio network consisting of a group of ...
[26]
LOCAL ANTIMAGIC LABELING OF CYCLE-RELATED GRAPHS ...
Oct 30, 2025 · The methodology involves assigning unique labels to edges to ensure neighboring vertices exhibit distinct label sums. Applied to wireless ...
[27]
On Radio Labeling of Diameter N-2 and Caterpillar Graphs
Radio labeling evolved as a way to use graph theory to try to solve the channel assignment problem: how to assign radio channels so that two radio transmitters ...Missing: allocation | Show results with:allocation
[28]
(PDF) Application of graph labeling in crystallography - ResearchGate
Aug 6, 2025 · In this paper, we examine the use of graph labeling in the area of material science especially in crystallography.
[29]
[PDF] Enhancing Data Security through Rainbow Antimagic Graph ... - arXiv
The implementation of Rainbow Antimagic coloring within these schemes not only safeguards the data but also ensures an advanced level of infor- mation security ...
[30]
Claimed proofs of graph labelling conjectures [closed] - MathOverflow
Nov 14, 2024 · A proof of the Kotzig-Ringel-Rosa Conjecture, https://arxiv.org/abs/2202.03178 ... On graceful labelings of trees, https://arxiv.org/abs/ ...
[31]
E-super vertex magic labelings of graphs - ScienceDirect.com
In [11] they proved the following: no super vertex magic total graph has two or more isolated vertices or an isolated edge; a tree with n internal edges and t n ...
[32]
Antimagic Orientation of Biregular Bipartite Graphs
Nov 3, 2017 · In this paper, we support this conjecture by proving that every biregular bipartite graph admits an antimagic orientation.
[33]
[2004.09947] Ringel's tree packing conjecture in quasirandom graphs
Apr 21, 2020 · Abstract:We prove that any quasirandom graph with n vertices and rn edges can be decomposed into n copies of any fixed tree with r edges.
[34]
A proof of Ringel's conjecture | Geometric and Functional Analysis
Sep 2, 2021 · In this paper, we study decompositions of complete graphs into large trees, where a tree is a connected graph with no cycles.
[35]
[2107.09025] The Spum and Sum-diameter of Graphs - math - arXiv
Jul 19, 2021 · We then provide asymptotically tight general bounds on both sides for the sum-diameter, and study its behavior under numerous binary graph ...