  The local minimum degree of a graph is the minimum degree reached by means of
a series of local complementations. In this paper, we investigate on this
quantity which plays an important role in quantum computation and quantum error
correcting codes. First, we show that the local minimum degree of the Paley
graph of order p is greater than sqrt{p} - 3/2, which is, up to our knowledge,
the highest known bound on an explicit family of graphs. Probabilistic methods
allows us to derive the existence of an infinite number of graphs whose local
minimum degree is linear in their order with constant 0.189 for graphs in
general and 0.110 for bipartite graphs. As regards the computational complexity
of the decision problem associated with the local minimum degree, we show that
it is NP-complete and that there exists no k-approximation algorithm for this
problem for any constant k unless P = NP.
