Flips in Graphs

Abstract

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|+|\{x\in V\setminus A:d_A(x)\text{is odd}\}|:A\ne \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)|=n\}$$ then we show that $f(n)\le (0.382+o(1))n$.