Proper connection number and connected dominating sets

The proper connection number pc(G)pc(G) of a connected graph G is defined as the minimum number of colors needed to color its edges, so that every pair of distinct vertices of G is connected by at least one path in G   such that no two adjacent edges of the path are colored the same, and such a path is called a proper path. In this paper, we show that for every connected graph with diameter 2 and minimum degree at least 2, its proper connection number is at most 3 and the bound is sharp. Then, we give an upper bound 3nδ+1−1 of the proper connection number for every connected graph of order n≥4n≥4 and minimum degree δ. We also show that for every connected graph G  , the proper connection number pc(G)pc(G) is upper bounded by pc(G[D])+2pc(G[D])+2, where D is a connected two-way (two-step) dominating set of G  . Bounds of the form pc(G)≤4pc(G)≤4 or pc(G)=2pc(G)=2, for many special graph classes follow as easy corollaries from this result, which include connected interval graphs, asteroidal triple-free graphs, circular arc graphs, threshold graphs and chain graphs, all with minimum degree at least 2. Furthermore, we get the sharp upper bound 3 for the proper connection numbers of interval graphs and circular arc graphs through analyzing their structures.