Bohman, Tom, Dudek, Andrzej, Frieze, Alan and Pikhurko, Oleg (2010) Flips in graphs. SIAM Journal on Discrete Mathematics, Vol.24 (No.3). pp. 1046-1055. doi:10.1137/090752237

Research output not available from this repository, contact author.

Request Changes to record.

Abstract

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\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\{f(G):\,|V(G)|=n\}$, then we show that $f(n)\leq(0.382+o(1))n$.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Mathematics
Journal or Publication Title:	SIAM Journal on Discrete Mathematics
Publisher:	Society for Industrial and Applied Mathematics
ISSN:	0895-4801
Official Date:	2010
Dates:	Date Event 2010 Published
Volume:	Vol.24
Number:	No.3
Page Range:	pp. 1046-1055
DOI:	10.1137/090752237
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access

Request changes or add full text files to a record

Repository staff actions (login required)

View Item