|
|
|
|
labeled graph
|
(Definition)
|
|
|
Let  be a graph with vertex set  and edge set  . A labeling of  is a partial function
 for some set  . For every  in the domain of  , the element
 is called the label of  . Three of the most common types of labelings of a graph  are
- total labeling:
 is a total function (defined for all of  ),
- vertex labeling: the domain of
 is  , and
- edge labeling: the domain of
 is  .
Usually,  above is assumed to be a set of integers. A labeled graph is a pair  where  is a graph and  is a labeling of  .
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)
| 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, tree, language, theory, order, areas, coloring, integers, total function, types, label, domain, partial function, edge, vertex, graph
There are 14 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 1613 times total.
Classification:
| AMS MSC: | 05C78 (Combinatorics :: Graph theory :: Graph labelling ) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
