Graphic sequences, distances and kk-degree anonymity

In this paper we study conditions to approximate a given graph by a regular one. We obtain optimal conditions for a few metrics such as the edge rotation distance for graphs, the rectilinear and the Euclidean distance over degree sequences. Then, we require the approximation to have at least kk copies of each value in the degree sequence, this is a property proceeding from data privacy that is called kk-degree anonymity.We give a sufficient condition in order for a degree sequence to be graphic that depends only on its length and its maximum and minimum degrees. Using this condition we give an optimal solution of kk-degree anonymity for the Euclidean distance when the sum of the degrees in the anonymized degree sequence is even. We present algorithms that may be used for obtaining all the mentioned anonymizations.