{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:43:08Z","timestamp":1787323388090,"version":"build-2736575974"},"reference-count":6,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>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$.<\/jats:p>","DOI":"10.1137\/090752237","type":"journal-article","created":{"date-parts":[[2010,8,24]],"date-time":"2010-08-24T18:11:23Z","timestamp":1282673483000},"page":"1046-1055","source":"Crossref","is-referenced-by-count":1,"title":["Flips in Graphs"],"prefix":"10.1137","volume":"24","author":[{"given":"Tom","family":"Bohman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrzej","family":"Dudek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alan","family":"Frieze","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Oleg","family":"Pikhurko","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,8,24]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"N. Alon and J. Spencer,\n                      The Probabilistic Method\n                      , 3rd ed., Wiley, New York, 2008.","DOI":"10.1002\/9780470277331"},{"key":"R2","unstructured":"M. Markus,\n                      Bounds on the minimum distance of linear codes and quantum codes\n                      , Fakult\u00e4t f\u00fcr Informatik, Universit\u00e4t Karlsruhe, Germany, http:\/\/codetables.de."},{"key":"R3","unstructured":"M. Hein, W. D\u00fcr, J. Eisert, R. Raussendorf, M. van den Nest, and H. J. Briegel,\n                      Entanglement in graph states and its applications\n                      , in Proceedings of the International School of Physics Enrico Fermi on Quantum Computers, Algorithms and Chaos, Varenna, Italy, 2006, arXiv:quant-ph\/0602096."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"J. H. van Lint,\n                      Introduction to Coding Theory\n                      , 3rd ed., Springer-Verlag, New York, 1999.","DOI":"10.1007\/978-3-642-58575-3"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.78.042303"},{"key":"R6","unstructured":"S. Yu, Q. Chen, and C. H. Oh,\n                      Graphical Quantum Error-correcting Codes\n                      , arXiv:0709.1780v1, 2007."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090752237","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:59:35Z","timestamp":1787320775000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090752237"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":6,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/090752237"],"URL":"https:\/\/doi.org\/10.1137\/090752237","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}