On (strong) proper vertex-connection of graphs

الأصل · EN

A path in a vertex-colored graph is a vertex-proper path if any two internal adjacent vertices differ in color. A vertex-colored graph is 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 proper vertex k-connection number of G, denoted by pvcₖ(G), is defined as the smallest number of colors required to make G proper vertex k-connected. A vertex-colored graph is 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 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ₖ(G), strong rainbow vertex-connection number srvc(G), and proper k-connection number pcₖ(G) of a k-connected graph G. Firstly, we determine the value of pvc(G) for general graphs and pvcₖ(G) for some specific graphs. We also compare the values of pvcₖ(G) and pcₖ(G). Then, sharp bounds of spvc(G) are given for a connected graph G of order n, that is, 0≤ spvc(G)≤ 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 χ(G) of a connected graph G.