Title: Is there any polynomial upper bound for the universal labeling of graphs?,
Abstract: A {\it universal labeling} of a graph $G$ is a labeling of the edge set in
$G$ such that in every orientation $\ell$ of $G$ for every two adjacent
vertices $v$ and $u$, the sum of incoming edges of $v$ and $u$ in the oriented
graph are different from each other. The {\it universal labeling number} of a
graph $G$ is the minimum number $k$ such that $G$ has {\it universal labeling}
from $\{1,2,\ldots, k\}$ denoted it by $\overrightarrow{\chi_{u}}(G) $. We have
$2\Delta(G)-2 \leq \overrightarrow{\chi_{u}} (G)\leq 2^{\Delta(G)}$, where
$\Delta(G)$ denotes the maximum degree of $G$. In this work, we offer a
provocative question that is:" Is there any polynomial function $f$ such that
for every graph $G$, $\overrightarrow{\chi_{u}} (G)\leq f(\Delta(G))$?".
Towards this question, we introduce some lower and upper bounds on their
parameter of interest. Also, we prove that for every tree $T$,
$\overrightarrow{\chi_{u}}(T)=\mathcal{O}(\Delta^3) $. Next, we show that for a
given 3-regular graph $G$, the universal labeling number of $G$ is 4 if and
only if $G$ belongs to Class 1. Therefore, for a given 3-regular graph $G$, it
is an $ \mathbf{NP} $-complete to determine whether the universal labeling
number of $G$ is 4. Finally, using probabilistic methods, we almost confirm a
weaker version of the problem.