{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,17]],"date-time":"2025-11-17T14:25:45Z","timestamp":1763389545528,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>Any finite simple graph $G = (V,E)$ can be represented by a collection $\\mathscr{C}$ of subsets of $V$ such that $uv\\in E$ if and only if $u$ and $v$ appear together in an odd number of sets in $\\mathscr{C}$. Let $c_2(G)$ denote the minimum cardinality of such a collection. This invariant is equivalent to the minimum dimension of a faithful orthogonal representation of $G$ over $\\mathbb{F}_2$ and is closely connected to the minimum rank of $G$. We show that $c_2 (G) = \\operatorname{mr}(G,\\mathbb{F}_2)$ when $\\operatorname{mr}(G,\\mathbb{F}_2)$ is odd, or when $G$ is a forest. Otherwise, $\\operatorname{mr}(G,\\mathbb{F}_2)\\leqslant c_2 (G)\\leqslant \\operatorname{mr}(G,\\mathbb{F}_2)+1$. Furthermore, we show that the following are equivalent for any graph $G$ with at least one edge: i. $c_2(G)=\\operatorname{mr}(G,\\mathbb{F}_2)+1$; ii. the adjacency matrix of $G$ is the unique matrix of rank $\\operatorname{mr}(G,\\mathbb{F}_2)$ which fits $G$ over $\\mathbb{F}_2$; iii. there is a minimum collection $\\mathscr{C}$ as described in which every vertex appears an even number of times; and iv. for every component $G'$ of $G$, $c_2(G') = \\operatorname{mr}(G',\\mathbb{F}_2) + 1$. We also show that, for these graphs, $\\operatorname{mr}(G,\\mathbb{F}_2)$ is twice the minimum number of tricliques whose symmetric difference of edge sets is $E$. Additionally, we provide a set of upper bounds on $c_2(G)$ in terms of the order, size, and vertex cover number of $G$. Finally, we show that the class of graphs with $c_2(G)\\leqslant k$ is hereditary and finitely defined. For odd $k$, the sets of minimal forbidden induced subgraphs are the same as those for the property $\\operatorname{mr}(G,\\mathbb{F}_2)\\leq k$, and we exhibit this set for $c_2(G) \\leqslant 2$.<\/jats:p>","DOI":"10.37236\/10383","type":"journal-article","created":{"date-parts":[[2022,2,24]],"date-time":"2022-02-24T12:19:33Z","timestamp":1645705173000},"source":"Crossref","is-referenced-by-count":7,"title":["Subgraph Complementation and Minimum Rank"],"prefix":"10.37236","volume":"29","author":[{"given":"Calum","family":"Buchanan","sequence":"first","affiliation":[]},{"given":"Christopher","family":"Purcell","sequence":"additional","affiliation":[]},{"given":"Puck","family":"Rombach","sequence":"additional","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2022,2,25]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v29i1p38\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v29i1p38\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,24]],"date-time":"2022-02-24T12:19:33Z","timestamp":1645705173000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v29i1p38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,25]]},"references-count":0,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,1,27]]}},"URL":"https:\/\/doi.org\/10.37236\/10383","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2022,2,25]]},"article-number":"P1.38"}}