On Oriented L(p, 1)-labeling

An oriented graph is a directed graph without any directed cycle of length at most 2. In this article, we characterize the oriented L(p, 1)-labeling span \(\lambda ^{o}_{p, 1}(\overrightarrow{G})\) of an oriented graph \(\overrightarrow{G}\) using graph homomorphisms. Using this characterization and probabilistic techniques we prove the upper bound of \(\lambda ^{o}_{p, 1}(\mathcal {G}_{\varDelta }) \le 2.\varDelta ^{2}.2^{\varDelta } + (p\varDelta )\), where \(\mathcal {G}_{\varDelta }\) is the family of graphs with maximum degree at most \(\varDelta \). Moreover, by proving a lower bound exponential in \(\varDelta \) for the same graph family we conclude that the upper bound is not too far from being optimal. We also settle an open problem given by Sen (DMGT 2014) for the family of outerplanar graphs \(\mathcal {O}\) by showing \(\lambda ^{o}_{2, 1}(\mathcal {O}) = 10\).