On the proper arc labeling of directed graphs
type: Item
instance of: scholarly article
title: On the proper arc labeling of directed graphs
zbMATH Open document ID: 1480.05110
author: A. Dehghan
author: A. Ahadi
published in: Graphs and Combinatorics
publication date: 2022-01-03T00:00:00Z
review text: 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.
reviewed by: P. Jeyanthi
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7451435
zbMATH Keywords: proper orientation
zbMATH Keywords: proper arc labeling
zbMATH Keywords: proper arc labeling number
zbMATH Keywords: optimal proper arc labeling
zbMATH Keywords: directed graph
MaRDI profile type: Publication
full work available at URL: s00373-021-02435-1
OpenAlex ID: W4200289184
cites work: The complexity of the proper orientation number
cites work: Is there any polynomial upper bound for the universal labeling of graphs?
cites work: Proper orientation number of triangle‐free bridgeless outerplanar graphs
cites work: On the proper orientation number of chordal graphs
cites work: On the proper orientation number of bipartite graphs
cites work: Proper orientation of cacti
cites work: Weighted proper orientations of trees and graphs of bounded treewidth
cites work: On the in-out-proper orientations of graphs
cites work: On the semi-proper orientations of graphs
cites work: On the complexity of deciding whether the regular number is at most two
cites work: Note on (semi-)proper orientation of some triangulated planar graphs
cites work: Proper orientations of planar bipartite graphs
cites work: Proper 3-orientations of bipartite planar graphs with minimum degree at least 3
cites work: Q4869540
DOI: 10.1007/S00373-021-02435-1
description: scientific article; zbMATH DE number 7451435