Is there any polynomial upper bound for the universal labeling of graphs?

A 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 universal labeling number of a graph G is the minimum number k such that G has universal labeling from $$\{1,2,\ldots , k\}$$ { 1 , 2 , … , k } denoted it by $$\overrightarrow{\chi _{u}}(G) $$ χ u → ( G ) . We have $$2\Delta (G)-2 \le \overrightarrow{\chi _{u}} (G)\le 2^{\Delta (G)}$$ 2 Δ ( G ) - 2 ≤ χ u → ( G ) ≤ 2 Δ ( G ) , where $$\Delta (G)$$ Δ ( 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)\le f(\Delta (G))$$ χ u → ( G ) ≤ f ( Δ ( 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) $$ χ u → ( T ) = O ( Δ 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 {N}}}{{\mathbf {P}}} $$ N P -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.