Graph labeling

A graceful labelling; vertex labels are in black and edge labels in red

A graph is known as graceful when its vertices are labeled from 0 to |E|, the size of the graph, and this labelling induces an edge labelling from 1 to |E|. For any edge e, the label of e is the positive difference between the two vertices incident with e. In other words, if e is incident with vertices labeled i and j, e will be labeled |i − j|. Thus, a graph G = (V, E) is graceful if and only if there exists an injection that induces a bijection from E to the positive integers up to |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 labelling 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]

An edge-graceful labelling on a simple graph without loops or multiple edges on p vertices and q edges is a labelling of the edges by distinct integers in {1, …, q} such that the labelling on the vertices induced by labelling 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 labelling.

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

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

${\displaystyle q(q+1)={\frac {p(p-1)}{2}}\mod p.}$

A "harmonious labelling" 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 labelling. 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 K_1,7 × K₂ provides an example of a graph that is not harmonious.[9]

A graph colouring is a subclass of graph labellings. Vertex colourings assign different labels to adjacent vertices, while edge colourings assign different labels to adjacent edges.[10]

A lucky labelling 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 neighbours 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 labelling with the integers {1, …, k}.[11]