Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Flips in graphs

Tools
- Tools
+ Tools

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.
Official URL: http://dx.doi.org/10.1137/090752237

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:
DateEvent
2010Published
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 View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us