Flips in Graphs

We study a problem motivated by a question related to quantum-error-correcting codes. Combinatorially, it involves the following graph parameter: $$f(G)=\min \{\mid A\mathrm{\mid }+\mathrm{\mid }\{x\in V\setminus A:d_A(x)\text{is odd}\}\mathrm{\mid }:A\mathrm{\ne }\mathrm{\varnothing }\},$$ where $V$ is the vertex set of $G$ and $d_A(x)$ is the number of neighbors of $x$ in $A$. We give asymptotically tight estimates of $f$ for the random graph $G_{n,p}$ when $p$ is constant. Also, if $$f(n)=\max \{f(G):\mid V(G)\mathrm{\mid }=n\}$$ then we show that $f(n)\le (0.382+o(1))n$.