Topological additive numbering of directed acyclic graphs

Abstract

We propose to study a problem that arises naturally from both TopologicalNumbering of Directed Acyclic Graphs, and Additive Coloring (also knownas Lucky Labeling). LetDbe a digraph andfa labeling of its verticeswith positive integers; denote byS(v) the sum of labels over all neighborsof each vertexv. The labelingfis calledtopological additive numberingifS(u)< S(v) for each arc (u, v) of the digraph. The problem asks to find theminimum numberkfor whichDhas a topological additive numbering withlabels belonging to{1, . . . , k}, denoted byηt(D).We characterize when a digraph has topological additive numberings, givea lower bound forηt(D) and provide an integer programming formulation forour problem. We also present some families for whichηt(D) can be computedin polynomial time. Finally, we prove that this problem isN P-Hard evenwhen its input is restricted to planar bipartite digraphs.