Graph labeling

In themathematicaldiscipline ofgraph theory,agraph labelingis the assignment of labels, traditionally represented byintegers,toedgesand/orverticesof agraph.

Formally, given a graphG= (V,E),avertex labelingis afunctionofVto a set of labels; a graph with such a function defined is called avertex-labeled graph.Likewise, anedge labelingis a function ofEto 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 graphgenerally 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.For many applications, the edges or vertices are given labels that are meaningful in the associated domain. For example, the edges may be assignedweightsrepresenting the "cost" of traversing between the incident vertices.

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 theoryandformal languagetheory it is convenient to consider labeledmultigraphs,i.e., a pair of vertices may be connected by several labeled edges.

History

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

Special cases

Graceful labeling

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 from0to|E|,the size of the graph, and if this vertex labeling induces an edge labeling from1to|E|.For any edgee,the label ofeis the positive difference between the labels of the two vertices incident withe.In other words, ifeis incident with vertices labelediandj,thenewill be labeled|i−j|.Thus, a graphG= (V,E)is graceful if and only if there exists an injection fromVto{0,..., |E|}that induces a bijection fromEto{1,..., |E|}.

In his original paper, Rosa proved that allEulerian graphswith sizeequivalentto1or2(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 Kotzighimself has called the effort to prove the conjecture a "disease".

Edge-graceful labeling

Main article:Edge-graceful labeling

An edge-graceful labeling on a simple graph without loops or multiple edges onpvertices andqedges 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 modulopassigns all values from 0 top− 1to the vertices. A graphGis 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 graphGis an injection from the vertices ofGto thegroupof integersmodulok,wherekis the number of edges ofG,that induces abijectionbetween the edges ofGand the numbers modulokby 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 cyclesare harmonious, as arePetersen graphs.It is conjectured that trees are all harmonious if one vertex label is allowed to be reused.The seven-pagebook graphK_1,7×K₂provides an example of a graph that is not harmonious.

Graph coloring

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.

Lucky labeling

A lucky labeling of a graphGis an assignment of positive integers to the vertices ofGsuch that ifS(v)denotes the sum of the labels on the neighbors ofv,thenSis a vertex coloring ofG.The "lucky number" ofGis the leastksuch thatGhas a lucky labeling with the integers{1,…,k}.