2019/05/08 by Dehghan, Ali
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1905.02867
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) ≠ 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χs (G), is min(D,w)∈ Γ maxv∈ V(G) S(D,w)(v) , where Γ 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 maxv∈ V(G) S(D,w)(v)= \overrightarrowχs (G) . In this work, we show that every graph 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χ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.