On the proper arc labeling of directed graphs (Q2062885)

An arc labeling $l$ of a directed graph $G$ with positive integers is proper if for any two adjacent vertices $v$, $u$, $S_l (v)\neq S_l (u)$, where $S_l (v)$ denotes the sum of labels of the arcs with head $v$. The proper arc labeling number of a directed graph $G$, denoted by $\chi_p(G)$, is $\min_l\in\Gamma\max_{(v\in V(G))}S_l(v)$, where $\Gamma$ is the set of proper arc labelings of $G$. A proper arc labeling $l$ of $G$ is optimal if $\max_{(v\in V(G))}S_l(v)=\chi_p(G)$. In this paper, the authors study the proper arc labeling number of graphs and present some lower and upper bounds. They prove that every directed graph $G$ has a (not necessarily optimal) proper arc labeling from $\{1,2,3\}$; every graph $G$ has an optimal proper arc labeling from $\{1,2,\dots,r+1\}$, where $r=\max\{\lceil(d_G^+ (v))/(d_G^-(V))\rceil+1:v\in V(G)\}$; if $G$ is a bipartite graph, then $\Delta^-(v)\leq\chi_p (G)\leq\Delta^-(v)+1$; for each constant number $c$, there is a directed tree $T$ such that it does not have any optimal proper arc labeling from $\{1,2,\dots,c\}$. Also, they show that there is a polynomial time algorithm to find the proper arc labeling number of directed trees. Further, they compute that the proper arc labeling number of planar directed graphs is NP-hard. Finally, they pose open problems for further research.