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,\dots ,k\}$ denoted it by $\overrightarrow{{\chi }_u}(G)$. We have $2\Delta (G)-2\le \overrightarrow{{\chi }_u}(G)\le 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)\le 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.

To appear in Journal of Combinatorial Optimization

References in corpus (1)

• Algorithmic complexity of proper labeling problems