Flips in Graphs

We study a problem motivated by a question related to quantumerror-correcting codes. Combinatorially, it involves the following graph parameter:

f(G) = min {|A| + |{x ∈ V \ A : dA(x) is odd}| : A 6= ∅} ,

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

f(n) = max {f(G) : |V (G)| = n}

then we show that f(n) ≤ (0.382 + o(1))n.