# 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 $\ell:V\cup E\to L$ for some set $L$. For every $x$ in the domain of $\ell$, the element $\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: $\ell$ is a total function (defined for all of $V\cup E$),

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

• edge labeling: the domain of $\ell$ is $E$.

Usually, $L$ above is assumed to be a set of integers. A labeled graph is a pair $(G,\ell)$ where $G$ is a graph and $\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 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