Algorithmic complexity of proper labeling problems

Abstract

A proper labeling of a graph is an assignment of integers to some elements of a graph, which may be the vertices, the edges, or both of them, such that we obtain a proper vertex coloring via the labeling subject to some conditions. The problem of proper labeling offers many variants and received a great interest during recent years. We consider the algorithmic complexity of some variants of the proper labeling problems, we present some polynomial time algorithms and $\mathbf{NP}$-completeness results for them.

Cited by in corpus (5)

• Is there any polynomial upper bound for the universal labeling of graphs?
• Algorithmic expedients for the S-labeling problem
• Sigma Partitioning: Complexity and Random Graphs
• On the algorithmic complexity of adjacent vertex closed distinguishing colorings number of graphs
• On the algorithmic complexity of decomposing graphs into regular/irregular structures