{
  "id": "1505.04986",
  "version": "v1",
  "published": "2015-05-19T13:16:37.000Z",
  "updated": "2015-05-19T13:16:37.000Z",
  "title": "On (strong) proper vertex-connection of graphs",
  "authors": [
    "Hui Jiang",
    "Xueliang Li",
    "Yingying Zhang",
    "Yan Zhao"
  ],
  "comment": "12 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A path in a vertex-colored graph is a {\\it vertex-proper path} if any two internal adjacent vertices differ in color. A vertex-colored graph is {\\it proper vertex $k$-connected} if any two vertices of the graph are connected by $k$ disjoint vertex-proper paths of the graph. For a $k$-connected graph $G$, the {\\it proper vertex $k$-connection number} of $G$, denoted by $pvc_{k}(G)$, is defined as the smallest number of colors required to make $G$ proper vertex $k$-connected. A vertex-colored graph is {\\it strong proper vertex-connected}, if for any two vertices $u,v$ of the graph, there exists a vertex-proper $u$-$v$ geodesic. For a connected graph $G$, the {\\it strong proper vertex-connection number} of $G$, denoted by $spvc(G)$, is the smallest number of colors required to make $G$ strong proper vertex-connected. These concepts are inspired by the concepts of rainbow vertex $k$-connection number $rvc_k(G)$, strong rainbow vertex-connection number $srvc(G)$, and proper $k$-connection number $pc_k(G)$ of a $k$-connected graph $G$. Firstly, we determine the value of $pvc(G)$ for general graphs and $pvc_k(G)$ for some specific graphs. We also compare the values of $pvc_k(G)$ and $pc_k(G)$. Then, sharp bounds of $spvc(G)$ are given for a connected graph $G$ of order $n$, that is, $0\\leq spvc(G)\\leq n-2$. Moreover, we characterize the graphs of order $n$ such that $spvc(G)=n-2,n-3$, respectively. Finally, we study the relationship among the three vertex-coloring parameters, namely, $spvc(G), \\ srvc(G)$ and the chromatic number $\\chi(G)$ of a connected graph $G$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-05-19T13:16:37.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C40",
      "05C38",
      "05C75"
    ],
    "keywords": [
      "connected graph",
      "vertex-colored graph",
      "strong rainbow vertex-connection number",
      "internal adjacent vertices differ",
      "strong proper vertex-connection number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150504986J"
    }
  }
}