A universal labeling of a graph G is a labeling of the edge set in G such that in every orientation (Formula presented.) 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 (Formula presented.) denoted it by (Formula presented.). We have (Formula presented.), where (Formula presented.) 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, (Formula presented.)?”. Towards this question, we introduce some lower and upper bounds on their parameter of interest. Also, we prove that for every tree T, (Formula presented.). 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 (Formula presented.)-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.

Additional Metadata
Keywords 1-2-3-Conjecture, Regular graphs, Trees, Universal labeling, Universal labeling number
Persistent URL dx.doi.org/10.1007/s10878-016-0107-8
Journal Journal of Combinatorial Optimization
Ahadi, A. (Arash), Dehghan, A. (Ali), & Saghafian, M. (Morteza). (2016). Is there any polynomial upper bound for the universal labeling of graphs?. Journal of Combinatorial Optimization, 1–11. doi:10.1007/s10878-016-0107-8