The proper (Vertex) connection numbers of cubic graphs
Abstract
A path in an edge-colored graph is called a proper path if any two adjacent edges of the path differ in color. An edge-colored graph is called proper k-connected if any two distinct vertices of the graph are connected by k internally pairwise vertex disjoint proper paths. The proper k-connection number of a k-connected graph G, denoted by pck(G), is defined as the smallest number of colors that are needed in order to make G proper k-connected. In this paper, we determine the proper k-connection numbers of circular ladders and Mobius ladders. Next, we determine the proper k-connection numbers of all small cubic graphs of order 8 or less. A path in a vertex-colored graph is a vertex proper path if any two internal adjacent vertices of the path differ in color. A vertex-colored graph is proper vertex k-connected if any two distinct vertices of the graph are connected by k internally pairwise vertex disjoint vertex proper paths. For a k-connected graph G, the proper vertex k-connection number of G, denoted by pvck(G), is defined as the smallest number of colors required to make G proper vertex k-connected. In this paper, we determine the proper vertex k-connection numbers of circular ladders and Mobius ladders. Next, we determine the proper vertex k-connection numbers of all small cubic graphs of order 8 or less.
