Hubbry Logo
Graph labelingGraph labelingMain
Open search
Graph labeling
Community hub
Graph labeling
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Graph labeling
Graph labeling
Graph labeling
View on Wikipedia
from Wikipedia

In the mathematical discipline of graph theory, a graph labeling is the assignment of labels, traditionally represented by integers, to edges and/or vertices of a graph.[1]

Formally, given a graph G = (V, E), a vertex labeling is a function of V to a set of labels; a graph with such a function defined is called a vertex-labeled graph. Likewise, an edge labeling is a function of E to a set of labels. In this case, the graph is called an edge-labeled graph.

When the edge labels are members of an ordered set (e.g., the real numbers), it may be called a weighted graph.

When used without qualification, the term labeled graph generally refers to a vertex-labeled graph with all labels distinct. Such a graph may equivalently be labeled by the consecutive integers { 1, …, |V| } , where |V| is the number of vertices in the graph.[1] For many applications, the edges or vertices are given labels that are meaningful in the associated domain. For example, the edges may be assigned weights representing the "cost" of traversing between the incident vertices.[2]

In the above definition a graph is understood to be a finite undirected simple graph. However, the notion of labeling may be applied to all extensions and generalizations of graphs. For example, in automata theory and formal language theory it is convenient to consider labeled multigraphs, i.e., a pair of vertices may be connected by several labeled edges.[3]

History

[edit]

Most graph labelings trace their origins to labelings presented by Alexander Rosa in his 1967 paper.[4] Rosa identified three types of labelings, which he called α-, β-, and ρ-labelings.[5] β-labelings were later renamed as "graceful" by Solomon Golomb, and the name has been popular since.

Special cases

[edit]

Graceful labeling

[edit]
Main article: Graceful labeling
A graceful labeling; vertex labels are in black and edge labels in red

A graph is known as graceful if its vertices are labeled from 0 to |E|, the size of the graph, and if this vertex labeling induces an edge labeling from 1 to |E|. For any edge e, the label of e is the positive difference between the labels of the two vertices incident with e. In other words, if e is incident with vertices labeled i and j, then e will be labeled |i − j|. Thus, a graph G = (V, E) is graceful if and only if there exists an injection from V to {0, ..., |E|} that induces a bijection from E to {1, ..., |E|}.

In his original paper, Rosa proved that all Eulerian graphs with size equivalent to 1 or 2 (mod 4) are not graceful. Whether or not certain families of graphs are graceful is an area of graph theory under extensive study. Arguably, the largest unproven conjecture in graph labeling is the Ringel–Kotzig conjecture, which hypothesizes that all trees are graceful. This has been proven for all paths, caterpillars, and many other infinite families of trees. Anton Kotzig himself has called the effort to prove the conjecture a "disease".[6]

Edge-graceful labeling

[edit]
Main article: Edge-graceful labeling

An edge-graceful labeling on a simple graph without loops or multiple edges on p vertices and q edges is a labeling of the edges by distinct integers in {1, …, q} such that the labeling on the vertices induced by labeling a vertex with the sum of the incident edges taken modulo p assigns all values from 0 to p − 1 to the vertices. A graph G is said to be "edge-graceful" if it admits an edge-graceful labeling.

Edge-graceful labelings were first introduced by Sheng-Ping Lo in 1985.[7]

A necessary condition for a graph to be edge-graceful is "Lo's condition":

Harmonious labeling

[edit]

A "harmonious labeling" on a graph G is an injection from the vertices of G to the group of integers modulo k, where k is the number of edges of G, that induces a bijection between the edges of G and the numbers modulo k by taking the edge label for an edge (x, y) to be the sum of the labels of the two vertices x, y (mod k). A "harmonious graph" is one that has a harmonious labeling. Odd cycles are harmonious, as are Petersen graphs. It is conjectured that trees are all harmonious if one vertex label is allowed to be reused.[8] The seven-page book graph K1,7 × K2 provides an example of a graph that is not harmonious.[9]

Graph coloring

[edit]
Main article: Graph coloring

A graph coloring is a subclass of graph labelings. Vertex colorings assign different labels to adjacent vertices, while edge colorings assign different labels to adjacent edges.[10]

Lucky labeling

[edit]

A lucky labeling of a graph G is an assignment of positive integers to the vertices of G such that if S(v) denotes the sum of the labels on the neighbors of v, then S is a vertex coloring of G. The "lucky number" of G is the least k such that G has a lucky labeling with the integers {1, …, k}.[11]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Graph labeling

View on Grokipedia
from Grokipedia
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. 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. 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). 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). 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. 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. 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.

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)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 VV; edge labelings, where labels are assigned solely to edges in EE; and total labelings, where labels are assigned to the union V∪EV \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 qq 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. 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 K2n+1K_{2n+1} can be decomposed into 2n+12n+1 edge-disjoint isomorphic copies of any tree with nn 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. 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→{1,2,…,∣V∣}f: V \to \{1, 2, \dots, |V|\}, of the maximum absolute difference ∣f(u)−f(v)∣|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 P3P_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.

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. In vertex labelings, integers are assigned to the vertices of a graph G=(V,E)G=(V,E), typically via a function f:V→N0f: V \to \mathbb{N}_0 (non-negative integers), such that the induced labels on edges—often defined as ∣f(u)−f(v)∣|f(u) - f(v)| or f(u)+f(v)f(u) + f(v) for an edge uv∈Euv \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→{0,1,…,∣E∣}f: V \to \{0,1,\dots,|E|\} that induces distinct edge differences {1,2,…,∣E∣}\{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. Edge labelings, in contrast, directly assign integers to the edges via g:E→Ng: 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 ∑e∋vg(e)\sum_{e \ni v} g(e) over edges ee incident to each vertex vv are distinct, as in antimagic labelings where edges receive {1,2,…,∣E∣}\{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. Total labelings extend this framework by assigning labels to both vertices and edges simultaneously, usually through a bijective function h:V∪E→{1,2,…,∣V∣+∣E∣}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)h(u) + h(uv) + h(v) being constant for every edge uvuv. Edge-magic total labelings exemplify this, requiring all such weights to equal a fixed integer kk, 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. 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.

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 K2m+1K_{2m+1} into m+1m+1 isomorphic subgraphs for trees with mm edges. 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. Concurrently, Solomon Golomb explored difference labelings in 1972, focusing on trees and assigning vertex labels from 0 to mm (for mm edges) so that edge differences are distinct integers from 1 to mm, 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.

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. Their work established proofs for caterpillars and other tree subclasses, fueling interest in the graceful tree conjecture. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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 January 2026, the conjecture is still open, with Gnang's claims and subsequent 2024 preprints unaccepted by the community. Recent work incorporates computational tools for verifying labelings on larger graphs, with Gallian's surveys highlighting persistent open problems like the graceful tree conjecture.

Graceful labelings and variants

Graceful labeling

A graceful labeling of a simple connected graph GG with qq edges is a bijection f:V(G)→{0,1,…,q}f: V(G) \to \{0, 1, \dots, q\} such that the induced edge labels ∣f(u)−f(v)∣|f(u) - f(v)| for each edge uv∈E(G)uv \in E(G) form the set {1,2,…,q}\{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 qq 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 PnP_n for all nn, stars K1,nK_{1,n} for all nn, caterpillars, and trees with diameter at most 5 or at most 4 endpoints are known to be graceful. For cycles, CnC_n is graceful if and only if n≡0(mod4)n \equiv 0 \pmod{4} or n≡3(mod4)n \equiv 3 \pmod{4}, as proven by Rosa for odd nn and extended to multiples of 4 by subsequent work. Complete bipartite graphs Km,nK_{m,n} (with m,n>1m, n > 1) are graceful, with explicit constructions provided for cases like K2,nK_{2,n} when nn 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 CnC_n with n≡1(mod4)n \equiv 1 \pmod{4} or n≡2(mod4)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 P3P_3 with vertices aa-bb-cc; the labeling f(a)=0f(a) = 0, f(b)=2f(b) = 2, f(c)=1f(c) = 1 induces edge labels ∣0−2∣=2|0-2| = 2 and ∣2−1∣=1|2-1| = 1, covering {1,2}\{1, 2\} distinctly. For a graceful cycle like C4C_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 qq.

Edge-graceful and odd-graceful labelings

An edge-graceful labeling of a graph GG with nn vertices and qq edges is a bijection g:E(G)→{1,2,…,q}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 nn, form the distinct values {0,1,…,n−1}\{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)≡n(n−1)/2(modn)q(q+1) \equiv n(n-1)/2 \pmod{n}. An odd-graceful labeling of a graph GG with qq edges is an injection f:V(G)→{0,1,…,2q−1}f: V(G) \to \{0, 1, \dots, 2q-1\} such that the induced edge labels ∣f(u)−f(v)∣|f(u) - f(v)| for each edge uvuv are the distinct odd integers {1,3,…,2q−1}\{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 CnC_n admit an odd-graceful labeling if and only if nn is even. For example, the path P2P_2 can be odd-gracefully labeled with vertices 0 and 3, yielding the edge label ∣3−0∣=3|3-0| = 3, the sole odd integer in {1,3,…,3}\{1, 3, \dots, 3\}. Additional classes such as caterpillars, lobsters, and certain bipartite graphs like complete bipartite graphs Km,nK_{m,n} with m≤nm \leq n have been shown to be odd-graceful.

Harmonious and magic labelings

Harmonious labeling

A harmonious labeling of a graph GG with qq edges is an injective function f:V(G)→{0,1,…,q}f: V(G) \to \{0, 1, \dots, q\} such that the induced edge labels f(u)+f(v)(modq+1)f(u) + f(v) \pmod{q+1} are all distinct for every edge uv∈E(G)uv \in E(G). A graph that admits such a labeling is called harmonious. This labeling allows for non-surjective vertex mappings, though when q+1q+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 qq, harmonious labeling employs modular sums to achieve distinctness modulo q+1q+1. All paths PnP_n with n≥1n \geq 1 admit harmonious labelings. For example, for P3P_3 (q=2q=2), label the vertices 0, 1, 2; the edge sums are 0+1=1(mod3)0+1 = 1 \pmod{3} and 1+2=3≡0(mod3)1+2 = 3 \equiv 0 \pmod{3}, which are distinct. Cycles CnC_n are harmonious if and only if nn is odd, as even cycles fail due to parity constraints on the sums modulo nn. Complete bipartite graphs Km,nK_{m,n} are harmonious precisely when min⁡(m,n)=1\min(m,n) = 1, reducing to stars, which are paths or trees. 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. Recent progress as of 2024 confirms the conjecture for trees of bounded degree. A sequential harmonious labeling is a bijective variant where ff maps onto {0,1,…,q}\{0, 1, \dots, q\}, coinciding with the standard definition for trees where ∣V∣=q+1|V| = q+1.

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. An edge-magic total labeling of a graph GG with vertex set VV of order v=∣V∣v = |V| and edge set EE of size e=∣E∣e = |E| is a bijection h:V∪E→{1,2,…,v+e}h: V \cup E \to \{1, 2, \dots, v+e\} such that h(u)+h(uv)+h(v)=kh(u) + h(uv) + h(v) = k for some constant kk and every edge uv∈Euv \in E. The magic constant kk is determined by the labeling as k=∑i=1v+ei+∑v∈V(deg⁡(v)−1)h(v)ek = \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,…,v}\{1, 2, \dots, v\} while edges receive {v+1,v+2,…,v+e}\{v+1, v+2, \dots, v+e\}. A vertex-magic total labeling is a bijection h:V∪E→{1,2,…,v+e}h: V \cup E \to \{1, 2, \dots, v+e\} such that for every vertex v∈Vv \in V, h(v)+∑vu∈Eh(vu)=kh(v) + \sum_{vu \in E} h(vu) = k, where the sum is over edges incident to vv. The super vertex-magic total labeling analogously assigns {1,2,…,v}\{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. Key results include that cycles CnC_n admit edge-magic total labelings for all n≥3n \geq 3, with super edge-magic total labelings existing precisely when nn is odd. Complete graphs KnK_n are edge-magic total if and only if n=1,2,3,5,n = 1, 2, 3, 5, or 66. Paths PnP_n are super edge-magic total for all n≥1n \geq 1. For C3≅K3C_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=9k=9 for each edge. MacDougall's conjecture posits that every regular graph of order at least 3, except K2K_2 and 2K32K_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.

Other prominent labelings

Cordial and product cordial labelings

A cordial labeling of a graph G=(V,E)G = (V, E) is a function f:V→{0,1}f: V \to \{0, 1\} such that the induced edge labeling f∗(uv)=∣f(u)−f(v)∣f^*(uv) = |f(u) - f(v)| assigns to each edge a label in {0,1}\{0, 1\}, the number of vertices labeled 0 and the number labeled 1 differ by at most 1 (i.e., ∣vf(0)−vf(1)∣≤1|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., ∣ef(0)−ef(1)∣≤1|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. 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. All cycles CnC_n (for n≥3n \geq 3) are cordial; for even nn, adjacent pairs of equal labels achieve the required parity balance. All bipartite graphs are cordial, leveraging the bipartition to assign labels that equalize counts within parts. However, the complete graph KnK_n is cordial if and only if n≤3n \leq 3, as larger nn leads to imbalances in edge label counts exceeding the threshold. For example, the cycle C4C_4 admits a cordial labeling by assigning 0 to two adjacent vertices and 1 to the other two adjacent vertices. This yields vf(0)=2v_f(0) = 2, vf(1)=2v_f(1) = 2, two edges with label 0 (the same-label edges), and two with label 1 (the differing-label edges), satisfying ∣ef(0)−ef(1)∣=0≤1|e_f(0) - e_f(1)| = 0 \leq 1. A product cordial labeling is defined analogously: f:V→{0,1}f: V \to \{0, 1\} induces edge labels f∗(uv)=f(u)f(v)∈{0,1}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.

Prime and antimagic labelings

A prime labeling of a graph GG with vertex set V(G)V(G) of order nn is a bijection f:V(G)→{1,2,…,n}f: V(G) \to \{1, 2, \dots, n\} such that for every edge uv∈E(G)uv \in E(G), gcd⁡(f(u),f(v))=1\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. For complete graphs KnK_n, prime labelings exist precisely when n≤3n \leq 3, as larger cliques require labeling adjacent vertices with coprime numbers from {1,2,…,n}\{1, 2, \dots, n\}, which becomes impossible due to the density of composites and shared factors among small integers. An antimagic labeling of a graph GG with edge set E(G)E(G) of size mm is a bijection g:E(G)→{1,2,…,m}g: E(G) \to \{1, 2, \dots, m\} such that the vertex weights wg(v)=∑e∋vg(e)w_g(v) = \sum_{e \ni v} g(e) are distinct for all vertices v∈V(G)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 P2P_2 (isomorphic to K2K_2) is antimagic; they specifically highlighted trees other than P2P_2 and verified it for paths, cycles, complete graphs, and wheels. 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 nn vertices with maximum degree at least n−3n - 3 is antimagic. A generalization is the (a,d)(a, d)-antimagic labeling, where the distinct vertex weights form an arithmetic progression starting at aa with common difference d>0d > 0; the standard antimagic labeling corresponds to d=1d=1. This variant has been studied for various graph classes, including paths and cycles, which admit such labelings for appropriate aa and dd. For example, consider the path P3P_3 with vertices u,v,wu, v, w and edges e1=uve_1 = uv, e2=vwe_2 = vw. Labeling g(e1)=1g(e_1) = 1, g(e2)=2g(e_2) = 2 yields weights wg(u)=1w_g(u) = 1, wg(v)=3w_g(v) = 3, wg(w)=2w_g(w) = 2, all distinct. 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. In cryptography, magic labelings contribute to key distribution protocols by providing structured assignments that enhance encryption schemes. Antimagic labelings are employed in wireless networks for frequency assignment, ensuring distinct sums for adjacent vertices to minimize interference in channel allocation. 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. 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. Cordial labelings assist in database management for query optimization, where balanced label counts facilitate efficient indexing and retrieval structures. Harmonious labelings generate sequences applicable in astronomy and radar systems, modeling periodic signals with unique sum properties for precise timing and positioning.

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. 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. 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. 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. This remains open, though it has been verified computationally for all such trees with fewer than 30 vertices. 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. This has been confirmed for many tree classes, such as paths, stars, and caterpillars, but the general case persists. 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. Recent advancements have resolved longstanding problems related to labeling. In 2021, Ringel's 1963 tree-packing conjecture—that the complete graph K2m+1K_{2m+1} decomposes into 2m+12m+1 copies of any tree with mm edges—was proven using probabilistic methods on quasirandom graphs. Independently, Montgomery, Pokrovskiy, and Sudakov established it via blow-up lemmas and equitable colorings. 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. Additionally, in 2021, Gómez and Kovář confirmed super vertex-magic total labelings for complete graphs KnK_n when n≡0(mod4)n \equiv 0 \pmod{4} and n>4n > 4, resolving a prior conjecture. 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.

References

  1. https://www.combinatorics.org/files/Surveys/ds6/ds6v25-2022.pdf
  2. http://www.cs.columbia.edu/~tim/teaching/cs4203/Rosa-GracefulLabelings.pdf
  3. https://epubs.siam.org/doi/10.1137/0601045
  4. https://iopscience.iop.org/article/10.1088/1742-6596/1531/1/012077/pdf
  5. https://arxiv.org/abs/2004.09947
  6. https://arxiv.org/abs/2001.02665
  7. https://arxiv.org/abs/2202.03178
  8. https://arxiv.org/abs/2410.13840
  9. https://arxiv.org/abs/2409.05280
  10. https://ajc.maths.uq.edu.au/pdf/22/ocr-ajc-v22-p177.pdf
  11. https://www.researchgate.net/publication/233792958_Cordial_Graphs_A_Weaker_Version_of_Graceful_and_Harmonious_Graphs
  12. https://www.malayajournal.org/articles/MJM082.pdf
  13. https://math.colgate.edu/~integers/t24/t24.pdf
  14. https://martin.baca.website.tuke.sk/docs/antimagic-Hartsfield.pdf
  15. https://www.math.cmu.edu/~zyilma/docs/zby_antimagiclargemaxdegree.pdf
  16. https://www.combinatorics.org/files/Surveys/ds6/ds6v0-1998.pdf
  17. https://www.malayajournal.org/articles/MJM0S201033.pdf
  18. https://www.mdpi.com/2227-7390/11/19/4132
  19. https://www.researchgate.net/publication/348996477_An_application_of_super_mean_and_magic_graphs_labeling_on_cryptography_system
  20. https://www.sciencedirect.com/science/article/abs/pii/S0096300319305326
  21. https://www.researchgate.net/publication/391677521_LOCAL_ANTIMAGIC_LABELING_OF_CYCLE-RELATED_GRAPHS_FOR_COMMUNICATION_CHANNEL_OPTIMIZATION_IN_WIRELESS_SENSOR_NETWORKS
  22. https://iro.uiowa.edu/esploro/outputs/doctoral/On-Radio-Labeling-of-Diameter-N-2/9983777089902771
  23. https://www.researchgate.net/publication/346429014_Application_of_graph_labeling_in_crystallography
  24. https://www.combinatorics.org/files/Surveys/ds6/ds6v26-2023.pdf
  25. https://mathoverflow.net/questions/482509/claimed-proofs-of-graph-labelling-conjectures
  26. https://www.sciencedirect.com/science/article/pii/S0166218X12001205
  27. https://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i4p31
  28. https://link.springer.com/article/10.1007/s00039-021-00576-2
  29. https://arxiv.org/abs/2107.09025
  30. https://www.combinatorics.org/files/Surveys/ds6/ds6v24-2021.pdf
Add your contribution
Related Hubs
Contribute something
User Avatar
No comments yet.