Flips in Graphs
Tom Bohman, Andrzej Dudek, ALAN M. FRIEZE, Oleg Pikhurko · SIAM Journal on Discrete Mathematics · 2010
We study a problem motivated by a question related to quantum error-correcting codes. Combinatorially, it involves the graph parameter $f(G)=\min\{|A|+|\{x\in V\setminus A:d_A(x)$ is $\text{odd}\}|:A eq\emptyset\}$, 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):\,|V(G)|=n\}$, then we show that $f(n)\leq(0.382+o(1))n$.