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	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