Flips in Graphs

<p>We study a problem motivated by a question related to quantumerror-correcting codes. Combinatorially, it involves the following graph parameter:</p> <p>f(G) = min {|A| + |{x ∈ V \ A : dA(x) is odd}| : A 6= ∅} ,</p> <p>where V is the vertex set of G and dA(x) is the number of neighbors of x in A. We give asymptotically tight estimates of f for the random graph Gn,p when p is constant. Also, if</p> <p>f(n) = max {f(G) : |V (G)| = n}</p> <p>then we show that f(n) ≤ (0.382 + o(1))n.</p>