The local minimum degree of a graph is the minimum degree that can be reached by means of local complementation. For any n, there exist graphs of order n which have a local minimum degree at least 0.189n, or at least 0.110n when restricted to bipartite graphs. Regarding the upper bound, we show that the local minimum degree is at most 3/8n+o(n) for general graphs and n/4 + o(n) for bipartite graphs, improving the known n/2 upper bound. We also prove that the local minimum degree is smaller than half of the vertex cover number (up to a logarithmic term). The local minimum degree problem is NP-Complete and hard to approximate. We show that this problem, even when restricted to bipartite graphs, is in W[2] and FPT-equivalent to the EVENSET problem, whose W[1]-hardness is a long standing open question. Finally, we show that the local minimum degree is computed by a O~*(1.938~n)-algorithm, and a O~*(1.466~n)-algorithm for the bipartite graphs.
展开▼
