Approximating degree sequences with regular graphic sequences (Extended Abstract)

We study conditions to approximate the degree sequence of 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 Euclidean distances over degree sequences. When we require the approximation to have at least k copies of each value in the degree sequence, that is, each value d in the degree sequence appears at least k times, the problem has a direct application in the context of data privacy when k-anonymity is required.