Topological Additive Numbering of Directed Acyclic Graphs

Abstract

We propose to study a problem that arises naturally from both Topological Numbering of Directed Acyclic Graphs, and Additive Coloring (also known as Lucky Labeling). Let $D$ be a digraph and $f$ a labeling of its vertices with positive integers; denote by $S(v)$ the sum of labels over all neighbors of each vertex $v$. The labeling $f$ is called \emph{topological additive numbering} if $S(u)<S(v)$ for each arc $(u,v)$ of the digraph. The problem asks to find the minimum number $k$ for which $D$ has a topological additive numbering with labels belonging to $\{1,\dots ,k\}$, denoted by ${\eta }_t(D)$. We characterize when a digraph has topological additive numberings, give a lower bound for ${\eta }_t(D)$, and provide an integer programming formulation for our problem, characterizing when its coefficient matrix is totally unimodular. We also present some families for which ${\eta }_t(D)$ can be computed in polynomial time. Finally, we prove that this problem is \np-Hard even when its input is restricted to planar bipartite digraphs.

References in corpus (2)

• Additive colorings of planar graphs
• On the Lucky labeling of Graphs

Cited by in corpus (1)

• On the additive chromatic number of several families of graphs