Graph labeling

From Wikipedia, the free encyclopedia

You have new messages (last change).

In the mathematical discipline of graph theory, a graph labeling is the assignment of unique identifiers to the edges and vertices of a graph.

Normally, the vertices of a graph by their nature are indistinguishable. (Of course, they may be distinguishable by the properties of the graph itself, e.g., by the numbers of incident edges). Some branches of graph theory require to uniquely identify vertices.

[edit] Definition

Given a mixed graph G: = (V,E,A) with V the vertices, E the edges and A the arcs of the graph, a vertex labeling is a bijective function

\nu:\lbrace 1,2, \ldots, \|V\| \rbrace \to V.

A graph with vertex labeling is called labeled or vertex labeled.

An edge labeling is a bijective function

\epsilon:\lbrace 1,2, \ldots, \|E\| \rbrace \to E.

A graph with edge labeling is called edge labeled.

An arc labeling is a bijective function

\alpha:\lbrace 1,2, \ldots, \|A\| \rbrace \to A.

A graph with arc labeling is called arc labeled.

A graph with vertex, edge and arc labeling is called completely labeled. A graph without vertex, edge or arc labeling is called unlabeled.

See also Multigraph Labeled graph

Retrieved from "http://en.wikipedia.org../../../g/r/a/Graph_labeling.html"