Affordable Access

Flips in graphs

Authors
Publisher
Society for Industrial and Applied Mathematics
Publication Date
Keywords
  • Qa Mathematics
Disciplines
  • Physics

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$.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Flips in Graphs

Mar 12, 2009

Flips in planar graphs

on Computational Geometry Jan 01, 2009

Maximal planar graphs of inscribable type and diag...

on Discrete Mathematics Jan 01, 2009

TCF-1 Flips the Switch on Eomes

on Immunity Jan 01, 2010
More articles like this..