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

Arash Ahadi, Ali Dehghan, Morteza Saghafian

Published 2017-01-23Version 1

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.