Flips in Graphs
| dc.creator | Bohman, Tom | |
| dc.creator | Dudek, Andrzej | |
| dc.creator | Frieze, Alan | |
| dc.creator | Pikhurko, Oleg | |
| dc.date | 2009-03-12 | |
| dc.date.accessioned | 2026-07-07T12:51:55Z | |
| dc.date.available | 2026-07-07T12:51:55Z | |
| dc.description | We study a problem motivated by a question related to quantum-error-correcting codes. Combinatorially, it involves the following graph parameter: $$f(G)=\min\set{|A|+|\{x\in V\setminus A : d_A(x)\text{is odd}\}| : A\neq\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\set{f(G): |V(G)|=n}$$ then we show that $f(n)\leq (0.382+o(1))n$. | |
| dc.identifier | https://arxiv.org/abs/0903.2201 | |
| dc.identifier | http://arxiv.org/abs/0903.2201 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/223141 | |
| dc.subject | Combinatorics | |
| dc.title | Flips in Graphs | |
| dc.type | text |