I would like to know the application of different graph labeling techniques in real life or practical situations. It will be highly appreciated if you share your knowledge in this area.
In the following paper you have an example of how a labelling scheme (a prime number labelling scheme in this case) is used to account for (capture) Web Entities Identity changes (ID revisions) due to merges or splits:
I am working in a problem related to prime number labelling schemes, so the applications I remember come mainly from here. Another example is that you can also use this type of labelling scheme to model and manage hierarchical data in relational databases:
But a diferent and surely important application is that of deriving a cannonical labelling of graphs (through Nauty software of Brendan Mackay for example) to solve the famous graph isomorphism problem (tell whether two diferent graphs are the same). This is important for example to distinguish molecules in Chemistry, since they can be represented as graphs whose edges/links are the atom bonds.
In the following paper you have an example of how a labelling scheme (a prime number labelling scheme in this case) is used to account for (capture) Web Entities Identity changes (ID revisions) due to merges or splits:
I am working in a problem related to prime number labelling schemes, so the applications I remember come mainly from here. Another example is that you can also use this type of labelling scheme to model and manage hierarchical data in relational databases:
But a diferent and surely important application is that of deriving a cannonical labelling of graphs (through Nauty software of Brendan Mackay for example) to solve the famous graph isomorphism problem (tell whether two diferent graphs are the same). This is important for example to distinguish molecules in Chemistry, since they can be represented as graphs whose edges/links are the atom bonds.
Ranking is a common problem needed in parallel or distributed computing (identifying processors or threads with identifiers). This corresponds to labelling vertices in a dependency graph or to mark processing elements in the system. Depending on the topology of the network, it can be an easy problem or quite a non-trivial one.
Also, labelling graphs and colouring graphs go hand-in-hand, so many of the situations where colouring arise, labelling tends to find its way in as well. For example, if I want to classify vertices in the process of labelling them can correspond to colouring vertices.
There are more, but these are two I can think of off the top of my head. As Fernando points out, labelling graphs and detecting isomorphisms tend to be useful to consider together (as permuting the labels will help in the venture, even through brute-force-and-ignorance).
See Section 1.2, starting on page 13, on graph labelings. Here are different types of graph labelings:
Graceful labeling. A vertex labeling f: G -> 2^Z a graph G is graceful, provided f is an injective mapping on the set of vertices of G into a set of integers (subset of Z) such that the induced map f*(xy) = |f(x) - f(y)|, for edge xy in G, assigns a different label to each edge of G. A sample graceful labeling is shown in the attached image.
Harmonious labeling. A vertex labeling f of a graph G is harmonious, provided f is an injective map on the vertex set to the additive group (Z, +) such that f*(xy) = f(x) + f(y) for every xy in the set of edges of G, assigns a different label to each edge in G.
Edge magic labeling. A bijection f: V(G) union E(G) --> {1, 2, ..., |V(G)|+|E(G|} is an edge magic total labeling of G, provided there is a positive integer h such that
f(x) + f(xy) + f(y) = h for each edge xy in G.
Distance magic labeling. A bijection on the set of vertices V(G) of G into the set {1,2,...,|V(G)|} such that the sum of the f(y) = k, a postive integer for y in V(G).
For a graphGwithpvertices andqedges, a vertex magic total labeling(VMTL) is a bijectionf:V(G)∪E(G)→ {1, 2, 3, . . . ,p+q} such that for every vertex u∈V(G), its weightwtf(u) =f(u) +∑v∈N(u)f(uv) =kfor some constant k (p. 3).
If you take a look at these four articles, in that order, you will be able to find (first article) a pretty simple graph labeling technique to enumerate a special class of graphs (called geodetic) homeomorphic to a given geodetic graph, which in turn can be applied, for instance (second article), to the topological construction of computer networks with optimum indices of their performance quality (and beyond, to the solution of fundamental problems related to transmission, processing, and analysis of data in complex computer systems.)
1.Article Geodetic Graphs Homeomorphic to a Given Geodetic Graph
2.Article Topological Analysis and Synthesis of Structures related to ...
3.Article Enumeration of labeled geodetic graphs with small cyclomatic number
4.Article K-Geodetic Graphs and their Applications to Analysis across ...