(Strong) Proper Connection in Some Digraphs

Abstract

An arc-colored digraph D is proper connected if any pair of vertices vi, vj ε V(D) there is a proper vi - vj path whose adjacent arcs have different colors and a proper vj - vi path whose adjacent arcs have different colors. The proper connection number of a digraph D is the minimum number of colors needed to make D proper connected, denoted by spc(D). An arc-colored digraph D is strong proper connected if any pair of vertices vi, vj ε V(D) there is a proper vi - vj geodesic and a proper vj - vi geodesic. The strong proper connection number of D is the minimum number of colors required to color the arcs of D in order to make D strong proper connected, denoted by spc(D). In this paper, we will show some results on spc(D) and spc(D), mostly for the case of the (strong) proper connection numbers of cacti and circulant digraphs.

Keywords

• Proper path
• proper connection number
• proper geodesic
• strong proper connection number