Labelability

Labelability is a property of a combinatorial structure that admits a labeling under a specified scheme. In mathematics, labelability most often concerns graphs, for which a labeling assigns labels from a prescribed set to vertices and/or edges according to prescribed rules. A graph is said to be labelable if such a labeling exists.

There are many labeling schemes. Graceful labeling requires vertex labels from 0 to m (the number of edges) such that the edge labels, defined as the absolute difference of endpoint labels, are all distinct and cover 1 through m. Harmonious labeling assigns vertex labels from a fixed range modulo q and requires edge labels (the sum of endpoint labels modulo q) to be distinct. Alpha-labeling, magic labeling, and other schemes impose variations on the range of labels and the constraints on induced edge or vertex values. A graph that satisfies the conditions of a given scheme is called labelable under that scheme.

Determining labelability is a decision problem whose difficulty depends on the scheme and the graph class. Some results are existence proofs for particular families; others yield NP-completeness or hardness results for certain schemes. The study of labelability connects to graph coloring, combinatorial design, and number theory, and continues to yield both constructive labelings and nonexistence proofs.

Note: Since labelability can refer to other domains, the exact definition is scheme-dependent and researchers specify the labeling rules in each context.