Fork me on GitHub
Math for the people, by the people.

User login

labeled graph


% used for TeXing text within eps files
% need this for including graphics (\includegraphics)
% for neatly defining theorems and propositions
% making logically defined graphics

% define commands here
\newcommand*{\abs}[1]{\left\lvert #1\right\rvert}
\newcommand{\pdiff}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\mpdiff}[3]{\frac{\partial^#1 #2}{\partial #3^#1}}
Let $G=(V,E)$ be a graph with vertex set $V$ and edge set $E$.  A \emph{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 \emph{label} of $x$.  Three of the most common types of labelings of a graph $G$ are
\item \emph{total labeling}: $\ell$ is a total function (defined for all of $V\cup E$),
\item \emph{vertex labeling}: the domain of $\ell$ is $V$, and
\item \emph{edge labeling}: the domain of $\ell$ is $E$.
Usually, $L$ above is assumed to be a set of integers.  A \emph{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 \emph{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.
The notion of labeling can be easily extended to digraphs, multigraphs, and pseudographs.