Graph labeling

From Wikipedia, the free encyclopedia

In the mathematical discipline of graph theory, a graph labeling is the assignment of labels, traditionally represented by integers, to the edges or vertices, or both, of a graph.^[1]

Formally, given a graph G: = (V,E) with V being the set of vertices and E being the set of edges, a vertex labeling is a function from some subset of the integers to the vertices of the graph. A graph with such a function defined is called a vertex-labeled graph. Likewise, an edge labeling is a function from some subset of the integers to the edges of the graph, which is likewise called an edge-labeled graph.

In many contexts, when used without additional qualifications, the term "labeled graph" refers to a vertex-labeled graph with all labels being different (and hence represented by consecutive integers 1,...,n, where n is the number of vertices of the graph).^[1] At the same time, in many other contexts the sets of edge and vertex labels may be arbitrary sets suitable for the application in question, e.g., a finite alphabet.^[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, in automata theory and formal language theory it is convenient to consider labeled multigraphs, i.e., a pair of vertices may be connected by several labeled edges.^[3]

Contents 1 History 2 Special cases 2.1 Graceful labeling 2.2 Harmonious labelings 2.3 Graph coloring 3 References

[edit] History

Most graph labelings trace their origins to labelings presented by Alex Rosa in his 1967 paper.^[4] Rosa identified three types of labelings, which he called α-, β-, and ρ-labelings.^[5] β-Labelings were later renamed graceful by S.W. Golomb and the name has been popular since.

[edit] Special cases

[edit] Graceful labeling

A graph is known as graceful when its vertices are labeled from 0 to , the size of the graph, and this labeling induces an edge labeling from 1 to . For any edge e, e's label is the positive difference between the two vertices incident with e. In other words, if e is incident with vertices labeled k and j, e will be labeled . 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 .

In his original paper, Rosa proved that all eulerian graphs with order 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 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. Kotzig himself has called the effort to prove the conjecture a "disease."

[edit] Harmonious labelings

A harmonious graph is a graph with k edges that permits an injection from the vertices of G to the group of integers modulo k that induces a bijection between the edges of G and the positive integers up to . For any edge e, e's label is the sum of the labels of the two vertices incident with e (mod q).

[edit] Graph coloring

Graph coloring is a special case of graph labelings, such that adjacent vertices and coincident edges must have different labels.

[edit] References

• Rosa, A. "On certain valuations of the vertices of a graph." Theory of Graphs (Internat. Symposium, Rome, July 1966), Gordon and Breach, N. Y. and Dunod Paris. (1967) 349-355.
• Gallian, Joseph A. "A Dynamic Survey of Graph Labeling." The Electronic Journal of Combinatorics (2005). 20 Dec. 2006 [1].