labeled graph


Let G=(V,E) be a graph with vertex set V and edge set E. A labeling of G is a partial functionMathworldPlanetmath :VEL for some set L. For every x in the domain of , the element (x)L is called the label of x. Three of the most common types of labelings of a graph G are

  • total labeling: is a total function (defined for all of VE),

  • vertex labeling: the domain of is V, and

  • edge labeling: the domain of is E.

Usually, L above is assumed to be a set of integers. A labeled graph is a pair (G,) where G is a graph and is a labeling of G.

An example of a labeling of a graph is a coloringMathworldPlanetmath of a graph. Uses of graph labeling outside of combinatorics can be found in areas such as order theory, languagePlanetmathPlanetmath theory, and proof theory. A proof tree, for instance, is really a labeled tree, where the labels of vertices are formulasMathworldPlanetmathPlanetmath, and the labels of edges are rules of inferenceMathworldPlanetmath.

Remarks.

  • Every labeling of a graph can be extended to a total labeling.

  • The notion of labeling can be easily extended to digraphsMathworldPlanetmath, multigraphsMathworldPlanetmath, and pseudographsMathworldPlanetmath.

Title labeled graph
Canonical name LabeledGraph
Date of creation 2013-03-22 17:38:19
Last modified on 2013-03-22 17:38:19
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 7
Author CWoo (3771)
Entry type Definition
Classification msc 05C78
Synonym labelled graph
Synonym graph labelling
Synonym labelling
Synonym vertex labelling
Synonym edge labelling
Synonym total labelling
Synonym labelled tree
Synonym labelled multigraph
Synonym labelled pseudograph
Defines graph labeling
Defines labeling
Defines vertex labeling
Defines edge labeling
Defines total labeling
Defines labeled tree
Defines labeled multigraph
Defines labeled pseudograph