Name
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$. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1137/090752237 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
random graph,random graphs | Discrete mathematics,Graph,Quantum,Combinatorics,Random graph,Vertex (geometry),Mathematics | Journal |
Volume | Issue | ISSN |
24 | 3 | 0895-4801 |
Citations | PageRank | References |
1 | 0.63 | 1 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tom Bohman | 1 | 250 | 33.01 |
| Andrzej Dudek | 2 | 114 | 23.10 |
| Alan M. Frieze | 3 | 4837 | 787.00 |
| Oleg Pikhurko | 4 | 318 | 47.03 |