A semi-proper orientation of a given graph $G$, denoted by $(D,w)$, is an orientation $D$ with a weight function $w: A(D)rightarrow mathbb{Z}_+$, such that the in-weight of any adjacent vertices are distinct, where the in-weight of $v$ in $D$, denoted by $w^-_D(v)$, is the sum of the weights of arcs towards $v$. The semi-proper orientation number of a graph $G$, denoted by $overrightarrow{chi}_s(G)$, is the minimum of maximum in-weight of $v$ in $D$ over all semi-proper orientation $(D,w)$ of $G$. This parameter was first introduced by Dehghan (2019). When the weights of all edges eqaul to one, this parameter is equal to the proper orientation number of $G$. The optimal semi-proper orientation is a semi-proper orientation $(D,w)$ such that $max_{vin V(G)}w_D^-(v)=overrightarrow{chi}_s(G)$. Araujo et al. (2016) showed that $overrightarrow{chi}(G)le 7$ for every cactus $G$ and the bound is tight. We prove that for every cactus $G$, $overrightarrow{chi}_s(G) le 3$ and the bound is tight. Ara{u}jo et al. (2015) asked whether there is a constant $c$ such that $overrightarrow{chi}(G)le c$ for all outerplanar graphs $G.$ While this problem remains open, we consider it in the weighted case. We prove that for every outerplanar graph $G,$ $overrightarrow{chi}_s(G)le 4$ and the bound is tight.
Download