labeled graph
Let $G=(V,E)$ be a graph with vertex set $V$ and edge set $E$. A labeling of $G$ is a partial function^{} $\mathrm{\ell}:V\cup E\to L$ for some set $L$. For every $x$ in the domain of $\mathrm{\ell}$, the element $\mathrm{\ell}(x)\in L$ is called the label of $x$. Three of the most common types of labelings of a graph $G$ are

•
total labeling: $\mathrm{\ell}$ is a total function (defined for all of $V\cup E$),

•
vertex labeling: the domain of $\mathrm{\ell}$ is $V$, and

•
edge labeling: the domain of $\mathrm{\ell}$ is $E$.
Usually, $L$ above is assumed to be a set of integers. A labeled graph is a pair $(G,\mathrm{\ell})$ where $G$ is a graph and $\mathrm{\ell}$ is a labeling of $G$.
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^{}.
Remarks.

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

•
The notion of labeling can be easily extended to digraphs^{}, multigraphs^{}, and pseudographs^{}.
Title  labeled graph 
Canonical name  LabeledGraph 
Date of creation  20130322 17:38:19 
Last modified on  20130322 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 