|
|
|
Viewing Version
2
of
'labeled graph'
|
[ view 'labeled graph'
|
back to history
]
| Title of object: |
labeled graph |
| Canonical Name: |
LabeledGraph |
| Type: |
Definition |
| Created on: |
2007-11-25 18:43:51 |
| Modified on: |
2007-11-25 22:16:22 |
| Classification: |
msc:05C78 |
| Defines: |
graph labeling, labeling, vertex labeling, edge labeling, total labeling, labeled tree, labeled multigraph, labeled pseudograph |
| Synonyms: |
labeled graph=labelled graph
labeled graph=graph labelling
labeled graph=labelling
labeled graph=vertex labelling
labeled graph=edge labelling
labeled graph=total labelling
labeled graph=labelled tree
labeled graph=labelled multigraph
labeled graph=labelled pseudograph |
Preamble:
\usepackage{amssymb,amscd}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{mathrsfs}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
\usepackage{amsthm}
% making logically defined graphics
\usepackage{xypic}
\usepackage{pst-plot}
\usepackage{psfrag}
% define commands here
\newcommand*{\abs}[1]{\left\lvert #1\right\rvert}
\newtheorem{prop}{Proposition}
\newtheorem{thm}{Theorem}
\newtheorem{ex}{Example}
\newcommand{\real}{\mathbb{R}}
\newcommand{\pdiff}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\mpdiff}[3]{\frac{\partial^#1 #2}{\partial #3^#1}} |
Content:
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}
\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$.
\end{itemize}
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.
\textbf{Remarks}.
\begin{itemize}
\item
Every labeling and vertex labeling of a graph can be extended to a total labeling.
\item
The notion of labeling can be easily extended to multigraphs and pseudographs.
\end{itemize} |
|
|
|
|
|
