论文标题
关于外平面图的半播种方向的注释
Note on semi-proper orientations of outerplanar graphs
论文作者
论文摘要
给定图$ g $的半杂制方向是$（d，w）$，是一个方向$ d $，具有重量函数$ w：a（d）\ rightarrow \ mathbb {z} _+$，以至于任何相邻的顶点的权威在$ v $ v $ v $ d $ v $ d $ v $ v $ v $ v $ d n p.弧的权重向$ v $的总和。图$ g $的半播种机导向数，由$ \toserrightArrowχ_s（g）$表示，是所有半传播$（d，w）$ g $的最小值最高$ v $ in $ d $。该参数首先由Dehghan（2019）引入。当所有边缘EQAUL的权重到一个时，此参数等于$ g $的适当方向数。最佳的半播种方向是半播种的方向$（d，w）$，因此$ \ max_ {v \ in v（g）} w_d^ - （v）= \oftrightRightArrowχ_s（g）$。 Araújo等。 （2016年）表明，每个仙人掌$ g $的$ \oferrightArrowχ（g）\ le 7 $，界限很紧。我们证明，对于每个仙人掌$ g $，$ \oferrightarrowχ_s（g）\ le 3 $，绑定很紧。 Araújo等。 （2015年）询问是否有一个常数$ c $，以至于所有外平面图$g。$ $ c $。我们证明，对于每个外平面图$ g，$ $ \ $ \oferrightarrowχ_s（g）\ le 4 $，界限很紧。
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χ_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_{v\in V(G)}w_D^-(v)=\overrightarrowχ_s(G)$. Araújo et al. (2016) showed that $\overrightarrowχ(G)\le 7$ for every cactus $G$ and the bound is tight. We prove that for every cactus $G$, $\overrightarrowχ_s(G) \le 3$ and the bound is tight. Araújo et al. (2015) asked whether there is a constant $c$ such that $\overrightarrowχ(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χ_s(G)\le 4$ and the bound is tight.
