Let be a graph with vertex set and edge set . A labeling of is a partial function for some set . For every in the domain of , the element is called the label of . Three of the most common types of labelings of a graph are
total labeling: is a total function (defined for all of ),
vertex labeling: the domain of is , and
edge labeling: the domain of is .
Usually, above is assumed to be a set of integers. A labeled graph is a pair where is a graph and is a labeling of .
An example of a labeling of a graph is a coloring of a graph. Uses of graph labeling outside of combinatorics can be found in areas such as order theory, language theory, and proof theory. A proof tree, for instance, is really a labeled tree, where the labels of vertices are formulas, and the labels of edges are rules of inference.
Every labeling of a graph can be extended to a total labeling.
|Date of creation||2013-03-22 17:38:19|
|Last modified on||2013-03-22 17:38:19|
|Last modified by||CWoo (3771)|