Proper vertex connection and graph operations

MaRDI QIDQ6286359zbMATH OpenFDO

Authors Yingying Zhang, Xiaoyu Zhu

Publication date 6 May 2017

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 $pv{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 $spvc(G)$, is the smallest number of colors required to make $G$ strong proper vertex-connected. In this paper, we study the proper vertex $k$-connection number and the strong proper vertex-connection number on the join of two graphs, the Cartesian, lexicographic, strong and direct product, and present exact values or upper bounds for these operations of graphs.

This page was built for publication: Proper vertex connection and graph operations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6286359)