| Version 2 |
Version 1 |
| Let $G=(V,E)$ be a graph. 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 |
Let $G=(V,E)$ be a graph. 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 |
| \begin{itemize} |
\begin{itemize} |
| \item \emph{total labeling}: $\ell$ is a total function (defined for all of $V\cup E$), |
\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{vertex labeling}: the domain of $\ell$ is $V$, and |
| \item \emph{edge labeling}: the domain of $\ell$ is $E$. |
\item \emph{edge labeling}: the domain of $\ell$ is $E$. |
| \end{itemize} |
\end{itemize} |
|
A \emph{labeled graph} is a pair $(G,\ell)$ where $G$ is a graph and $\ell$ is a labeling of $G$.
|
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 \emph{labeled tree}, where the labels of vertices are formulas, and the labels of edges are rules of inference. |
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. |
|
|
| \textbf{Remarks}. |
\textbf{Remarks}. |
| \begin{itemize} |
\begin{itemize} |
| \item |
\item |
| Every labeling and vertex labeling of a graph can be extended to a total labeling. |
Every labeling and vertex labeling of a graph can be extended to a total labeling. |
| \item |
\item |
| The notion of labeling can be easily extended to multigraphs and pseudographs. |
The notion of labeling can be easily extended to multigraphs and pseudographs. |
| \end{itemize} |
\end{itemize} |
