In themathematical discipline ofgraph theory, agraph labeling is the assignment of labels, traditionally represented byintegers, toedges and/orvertices of agraph.[1]
Formally, given a graphG = (V,E), avertex labeling is afunction ofV to a set of labels; a graph with such a function defined is called avertex-labeled graph. Likewise, anedge labeling is a function ofE to a set of labels. In this case, the graph is called anedge-labeled graph.
When the edge labels are members of anorderedset (e.g., thereal numbers), it may be called aweighted graph.
When used without qualification, the termlabeled 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 assignedweights 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, inautomata theory andformal language theory it is convenient to consider labeledmultigraphs, i.e., a pair of vertices may be connected by several labeled edges.[3]
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" bySolomon Golomb, and the name has been popular since.
A graph is known as graceful if its vertices are labeled from0 to|E|, the size of the graph, and if this vertex labeling induces an edge labeling from1 to|E|. For any edgee, the label ofe is the positive difference between the labels of the two vertices incident withe. In other words, ife is incident with vertices labeledi andj, thene will be labeled|i −j|. Thus, a graphG = (V,E) is graceful if and only if there exists an injection fromV to{0, ..., |E|} that induces a bijection fromE to{1, ..., |E|}.
In his original paper, Rosa proved that allEulerian graphs with sizeequivalent to1 or2 (mod4) 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 allpaths,caterpillars, and many other infinite families of trees.Anton Kotzig himself has called the effort to prove the conjecture a "disease".[6]
An edge-graceful labeling on a simple graph without loops or multiple edges onp vertices andq 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 modulop assigns all values from 0 top − 1 to the vertices. A graphG 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":
A "harmonious labeling" on a graphG is an injection from the vertices ofG to thegroup of integersmodulok, wherek is the number of edges ofG, that induces abijection between the edges ofG and the numbers modulok by taking the edge label for an edge(x,y) to be the sum of the labels of the two verticesx,y (modk). A "harmonious graph" is one that has a harmonious labeling.Odd cycles are harmonious, as arePetersen graphs. It is conjectured that trees are all harmonious if one vertex label is allowed to be reused.[8] The seven-pagebook graphK1,7 ×K2 provides an example of a graph that is not harmonious.[9]
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]
A lucky labeling of a graphG is an assignment of positive integers to the vertices ofG such that ifS(v) denotes the sum of the labels on the neighbors ofv, thenS is a vertex coloring ofG. The "lucky number" ofG is the leastk such thatG has a lucky labeling with the integers{1, …,k}.[11]
Anantimagic labeling of a graphG is a one-to-one assignment of the positive integers{1,..., |E|} to the edges ofG such that all induced vertex weights are distinct, where theweight of a vertex is the sum of the labels on all edges incident to it.[12]
A(distance) magic labeling of a graphG is a one-to-one assignment of the positive integers{1,..., |V|} to the vertices ofG such that all vertex weights are equal to some positive integerk. Theweight of a vertex is the sum of the labels of all vertices adjacent to it. Such a constantk, if it exists, is calledmagic constant of a graph.