On the proper arc labeling of directed graphs (Q2062885)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On the proper arc labeling of directed graphs
scientific article

    Statements

    On the proper arc labeling of directed graphs (English)
    0 references
    0 references
    0 references
    3 January 2022
    0 references
    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.
    0 references
    0 references
    proper orientation
    0 references
    proper arc labeling
    0 references
    proper arc labeling number
    0 references
    optimal proper arc labeling
    0 references
    directed graph
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references