{
  "id": "1512.00726",
  "version": "v1",
  "published": "2015-12-02T15:01:51.000Z",
  "updated": "2015-12-02T15:01:51.000Z",
  "title": "Total proper connection of graphs",
  "authors": [
    "Hui Jiang",
    "Xueliang Li",
    "Yingying Zhang"
  ],
  "comment": "15 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A graph is said to be {\\it total-colored} if all the edges and the vertices of the graph is colored. A path in a total-colored graph is a {\\it total proper path} if $(i)$ any two adjacent edges on the path differ in color, $(ii)$ any two internal adjacent vertices on the path differ in color, and $(iii)$ any internal vertex of the path differs in color from its incident edges on the path. A total-colored graph is called {\\it total-proper connected} if any two vertices of the graph are connected by a total proper path of the graph. For a connected graph $G$, the {\\it total proper connection number} of $G$, denoted by $tpc(G)$, is defined as the smallest number of colors required to make $G$ total-proper connected. These concepts are inspired by the concepts of proper connection number $pc(G)$, proper vertex connection number $pvc(G)$ and total rainbow connection number $trc(G)$ of a connected graph $G$. In this paper, we first determine the value of the total proper connection number $tpc(G)$ for some special graphs $G$. Secondly, we obtain that $tpc(G)\\leq 4$ for any $2$-connected graph $G$ and give examples to show that the upper bound $4$ is sharp. For general graphs, we also obtain an upper bound for $tpc(G)$. Furthermore, we prove that $tpc(G)\\leq \\frac{3n}{\\delta+1}+1$ for a connected graph $G$ with order $n$ and minimum degree $\\delta$. Finally, we compare $tpc(G)$ with $pvc(G)$ and $pc(G)$, respectively, and obtain that $tpc(G)>pvc(G)$ for any nontrivial connected graph $G$, and that $tpc(G)$ and $pc(G)$ can differ by $t$ for $0\\leq t\\leq 2$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-12-02T15:01:51.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C40",
      "05C69",
      "05C75"
    ],
    "keywords": [
      "connected graph",
      "total proper connection number",
      "path differ",
      "total proper path",
      "upper bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}