Graceful labeling A graph is known as graceful if its vertices are labeled from to , the size of the graph, and if this vertex labeling induces an edge labeling from to . For any edge , the label of is the positive difference between the labels of the two vertices incident with . In other words, if is incident with vertices labeled and , then will be labeled . Thus, a graph is graceful if and only if there exists an injection from to {{math|{0, ..., }}} that induces a bijection from to {{math|{1, ..., }}}. In his original paper, Rosa proved that all
Eulerian graphs with size
equivalent to or (Modular arithmetic| ) 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".
Edge-graceful labeling An edge-graceful labeling on a simple graph without loops or multiple edges on vertices and edges is a labeling of the edges by distinct integers in {{math|{1, …,
q} }} such that the labeling on the vertices induced by labeling a vertex with the sum of the incident edges taken modulo assigns all values from 0 to to the vertices. A graph 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. A necessary condition for a graph to be edge-graceful is "Lo's condition": :q(q + 1) = \frac{p(p - 1)}{2} \mod p.
Harmonious labeling A "harmonious labeling" on a graph is an injection from the vertices of to the
group of integers
modulo , where is the number of edges of , that induces a
bijection between the edges of and the numbers modulo by taking the edge label for an edge to be the sum of the labels of the two vertices . 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. The seven-page
book graph provides an example of a graph that is not harmonious.
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.
Lucky labeling A lucky labeling of a graph is an assignment of positive integers to the vertices of such that if denotes the sum of the labels on the neighbors of , then is a vertex coloring of . The "lucky number" of is the least such that has a lucky labeling with the integers {{math|{1, …,
k}.}} ===
Antimagic labeling === An
antimagic labeling of a graph is a one-to-one assignment of the positive integers {{math|{1,..., }}} to the edges of such that all induced vertex weights are distinct, where the
weight of a vertex is the sum of the labels on all edges incident to it. ===
Magic labeling === A
(distance) magic labeling of a graph is a one-to-one assignment of the positive integers {{math|{1,..., }}} to the vertices of such that all vertex weights are equal to some positive integer . The
weight of a vertex is the sum of the labels of all vertices adjacent to it. Such a constant , if it exists, is called
magic constant of a graph. ==References==