Note on semi-proper orientations of outerplanar graphs

Authors Ruijuan Gu, G. Gutin, Yongtang Shi, Zhenyu Taoqiu

Publication date 15 April 2020

Abstract: A semi-proper orientation of a given graph

G

, denoted by

(D, w)

, is an orientation

D

with a weight function

w : A (D) i g h t a r r o w m a t h b b 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

o v e r r i g h t a r r o w {c h i}_{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

m a x_{v i n V (G)} w_{D}^{-} (v) = o v e r r i g h t a r r o w {c h i}_{s} (G)

. Ara'ujo et al. (2016) showed that

o v e r r i g h t a r r o w c h i (G) l e 7

for every cactus

G

and the bound is tight. We prove that for every cactus

G

,

o v e r r i g h t a r r o w {c h i}_{s} (G) l e 3

and the bound is tight. Ara'{u}jo et al. (2015) asked whether there is a constant

c

such that

o v e r r i g h t a r r o w c h i (G) l e 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,

o v e r r i g h t a r r o w {c h i}_{s} (G) l e 4

and the bound is tight.

This page was built for publication: Note on semi-proper orientations of outerplanar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6338727)