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

Seen <100 times

More articles like this

Mar 12, 2009

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
More articles like this..