{
  "id": "1701.06685",
  "version": "v1",
  "published": "2017-01-23T23:49:48.000Z",
  "updated": "2017-01-23T23:49:48.000Z",
  "title": "Is there any polynomial upper bound for the universal labeling of graphs?",
  "authors": [
    "Arash Ahadi",
    "Ali Dehghan",
    "Morteza Saghafian"
  ],
  "comment": "To appear in Journal of Combinatorial Optimization",
  "doi": "10.1007/s10878-016-0107-8",
  "categories": [
    "math.CO"
  ],
  "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,\\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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-01-23T23:49:48.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "polynomial upper bound",
      "universal labeling number",
      "edge set",
      "weaker version",
      "minimum number"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "publisher": "Springer"
    },
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}