You are here
Homelabeled graph
Primary tabs
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.
Mathematics Subject Classification
05C78 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections