Total proper connection of graphs

Hui Jiang, Xueliang Li, Yingying Zhang

Published 2015-12-02Version 1

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$.