In graph theory, graph labelling is an assignment of labels to the vertices and/or edges of a graph with respect to certain restrictions and in accordance with certain predefined rules. For the past few decades, graph labelling has become a fruitful research area in graph theory. Different graph labellings have resulted from practical considerations. They are not only of theoretical interests but have many practical implications also. For many applications, the edges or vertices of a given graph are given labels that are meaningful in the context.
Graph Labelling
Valuation of a graph is a one to one mapping of the vertex set of on to the set of all integers . Graph labeling has become a fertile research area in graph theory after the introduction of the notion of certain types number valuations, called -valuations, of graphs in Rosa (1967). The most popular one among the number valuations of graphs is -valuation or graceful labelling of a graph (see Golomb, 1972; Rosa, 1967) which is defined as an injective function
such that, when each edge
is assigned the label
, the resulting edge labels are distinct. A graph
is said to be
edge-graceful if there exists a bijection
such that the induced mapping
given by
taken over all edges
is a bijection.
Motivated by various problems in social networks, a set analogue of number valuations called set-valuation of graphs, has been introduced in Acharya (1983). In the number valuations, the elements of a graph are assigned to numbers while in the set-valuations, the elements of a graph are assigned to sets subject to certain conditions. The mathematical definition of a set-valuation of a graph concerned is as given below (see Acharya, 1983):
For a graph and a non-empty set , a set-labeling or a set-valuation of , with respect to the set , is an injective set-valued function
such that the function
is defined by
for every
, where
is the set of all subsets of
and
is the symmetric difference of sets. The definition can be generalised by allowing any binary operation
of two sets in place of the symmetric difference
in the above definitions.
Many significant and interesting studies on set-labelling of graphs have been done in the last two decades (see [1-10, 32, 33, 91]).