Proper connection number and connected dominating sets

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