On the semi-proper orientations of graphs

A {\it semi-proper orientation} of a given graph $G$ is a function $(D,w)$ that assigns an orientation $D(e)$ and a positive integer weight $w(e)$ to each edge $e$ such that for every two adjacent vertices $v$ and $u$, $S_{(D,w)}(v)\mathrm{\ne }{S}_{(D,w)}(u)$, where $S_{(D,w)}(v)$ is the sum of the weights of edges with head $v$ in $D$. The {\it semi-proper orientation number} of a graph $G$, denoted by ${\overrightarrow{\chi }}_s(G)$, is $ \min_{(D,w)\in \Gamma} \max_{v\in V(G)} S_{(D,w)}(v) $,where$\Gamma$ is the set of all semi-proper orientations of $G$. The {\it optimal semi-proper orientation} is a semi-proper orientation $(D,w)$ such that $ \max_{v\in V(G)} S_{(D,w)}(v)= \overrightarrow{\chi}_s (G) $\mathrm{.}Inthiswork,weshowthateverygraph$G$ has an optimal semi-proper orientation $(D,w)$ such that the weight of each edge is one or two. Next, we show that determining whether a given planar graph $G$ with ${\overrightarrow{\chi }}_s(G)=2$ has an optimal semi-proper orientation $(D,w)$ such that the weight of each edge is one is NP-complete. Finally, we prove that the problem of determining the semi-proper orientation number of planar bipartite graphs is NP-hard.