Graph Labeling

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.

Formally, given a graph G, a vertex labeling is a function mapping vertices of G to a set of labels. A graph with such a function defined is called a vertex-labeled graph. Likewise, an edge labeling is a function mapping edges of G to a set of "labels". In this case, G is called an edge-labeled graph. When the edge labels are members of an ordered set (e.g., the real numbers), it may be called a weighted graph.

When used without qualification, the term labeled graph generally refers to a vertex-labeled graph with all labels distinct. Such a graph may equivalently be labeled by the consecutive integers {1, ..., n}, where n 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 assigned weights representing 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, 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.

Read more about Graph LabelingHistory

Other articles related to "graph labeling, labeling, graph":

Graph Labeling - Special Cases - Lucky Labeling
... A lucky labeling 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 labeling with the integers {1...k} ...

Famous quotes containing the words labeling and/or graph:

    Although adults have a role to play in teaching social skills to children, it is often best that they play it unobtrusively. In particular, adults must guard against embarrassing unskilled children by correcting them too publicly and against labeling children as shy in ways that may lead the children to see themselves in just that way.
    Zick Rubin (20th century)

    When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.
    Marshall McLuhan (1911–1980)