{
  "id": "1204.2306",
  "version": "v1",
  "published": "2012-04-10T23:52:07.000Z",
  "updated": "2012-04-10T23:52:07.000Z",
  "title": "Path covering number and L(2,1)-labeling number of graphs",
  "authors": [
    "Changhong Lu",
    "Qing Zhou"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "A {\\it path covering} of a graph $G$ is a set of vertex disjoint paths of $G$ containing all the vertices of $G$. The {\\it path covering number} of $G$, denoted by $P(G)$, is the minimum number of paths in a path covering of $G$. An {\\sl $k$-L(2,1)-labeling} of a graph $G$ is a mapping $f$ from $V(G)$ to the set ${0,1,...,k}$ such that $|f(u)-f(v)|\\ge 2$ if $d_G(u,v)=1$ and $|f(u)-f(v)|\\ge 1$ if $d_G(u,v)=2$. The {\\sl L(2,1)-labeling number $\\lambda (G)$} of $G$ is the smallest number $k$ such that $G$ has a $k$-L(2,1)-labeling. The purpose of this paper is to study path covering number and L(2,1)-labeling number of graphs. Our main work extends most of results in [On island sequences of labelings with a condition at distance two, Discrete Applied Maths 158 (2010), 1-7] and can answer an open problem in [On the structure of graphs with non-surjective L(2,1)-labelings, SIAM J. Discrete Math. 19 (2005), 208-223].",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-04-10T23:52:07.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "vertex disjoint paths",
      "main work extends",
      "study path covering number",
      "open problem",
      "discrete applied maths"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1204.2306L"
    }
  }
}