Graph labeling

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 undistinguishable. (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.

Definition

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

.

A graph with vertex labeling is called vertex labeled.

An edge labeling is a bijective function

.

A graph with edge labeling is called edge labeled.

An arrow labeling is a bijective function

.

A graph with arrow labeling is called arrow labeled.

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