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

Original · EN

A universal labeling of a graph G is a labeling of the edge set in G such that in every orientation ℓ 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,, k} denoted it by χᵤ(G). We have 2Δ(G)-2 ≤ χᵤ (G)≤ 2Δ⁽ᵍ⁾, where Δ(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, χᵤ (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, χᵤ(T)=O(Δ³). 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 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.