|
|
|
|
labeled graph
|
(Definition)
|
|
|
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.
|
"labeled graph" is owned by CWoo.
|
|
(view preamble | get metadata)
| Other names: |
labelled graph, graph labelling, labelling, vertex labelling, edge labelling, total labelling, labelled tree, labelled multigraph, labelled pseudograph |
| Also defines: |
graph labeling, labeling, vertex labeling, edge labeling, total labeling, labeled tree, labeled multigraph, labeled pseudograph |
|
|
Cross-references: pseudographs, multigraphs, digraphs, rules of inference, formulas, tree, proof, language, theory, order, areas, coloring, integers, total function, types, label, element, domain, partial function, edge, vertex, graph
There are 18 references to this entry.
This is version 3 of labeled graph, born on 2007-11-25, modified 2007-11-26.
Object id is 10060, canonical name is LabeledGraph.
Accessed 7549 times total.
Classification:
| AMS MSC: | 05C78 (Combinatorics :: Graph theory :: Graph labelling ) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
