LAUSR

For an edge-colored graph G , a set F of edges of G is called a proper edge-cut if F is an edge-cut of G and any pair of adjacent edges in F are assigned different colors. An edge-colored graph is proper disconnected if for each pair of distinct vertices of G there exists a proper edge-cut separating them. For a connected graph G , the proper disconnection number of G , denoted by pd ( G ), is the minimum number of colors that are needed in order to make G proper disconnected. In this paper, we first give the exact values of the proper disconnection numbers for some special families of graphs. Next, we obtain a sharp upper bound of pd ( G ) for a connected graph G of order n , i.e, $$pd(G)\le \min \{ \chi '(G)-1, \left\lceil \frac{n}{2} \right\rceil \}$$ p d ( G ) ≤ min { χ ′ ( G ) - 1 , n 2 } . Finally, we show that for given integers k and n , the minimum size of a connected graph G of order n with $$pd(G)=k$$ p d ( G ) = k is $$n-1$$ n - 1 for $$k=1$$ k = 1 and $$n+2k-4$$ n + 2 k - 4 for $$2\le k\le \lceil \frac{n}{2}\rceil $$ 2 ≤ k ≤ ⌈ n 2 ⌉ .