Degree anonymization by vertex addition is computationally intractable in general.
Posing structural restrictions on the edges connected to the new vertices seems to make the problem even harder.
There are some tractable special cases, for example, when the number of new edges is small.