paper

On (strong) proper vertex-connection of graphs

arXiv:1505.04986

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 $p v c_{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 $s p v c (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 $r v c_{k} (G)$ , strong rainbow vertex-connection number $sr v c (G)$ , and proper $k$ -connection number $p c_{k} (G)$ of a $k$ -connected graph $G$ . Firstly, we determine the value of $p v c (G)$ for general graphs and $p v c_{k} (G)$ for some specific graphs. We also compare the values of $p v c_{k} (G)$ and $p c_{k} (G)$ . Then, sharp bounds of $s p v c (G)$ are given for a connected graph $G$ of order $n$ , that is, $0 \leq s p v c (G) \leq n - 2$ . Moreover, we characterize the graphs of order $n$ such that $s p v c (G) = n - 2, n - 3$ , respectively. Finally, we study the relationship among the three vertex-coloring parameters, namely, $s p v c (G), sr v c (G)$ and the chromatic number $I ¨ (G)$ of a connected graph $G$ .

12 pages