Topological additive numbering of directed acyclic graphs ?
We define and study a problem which we call Topological Additive Numbering of Directed Acyclic Graphs. We prove that the existence of a topological additive numbering in a digraph is polynomial. We give a lower bound of the parameter in terms of a clique of the digraph. We give the exact value of the parameter for certain families of digraphs. We prove that the problem is NP-Hard even when the digraph is planar and bipartite.
topological additive numbering directed acyclic graphs additive coloring lucky labeling computational complexity