Terminology for expressing a graph as a sum of cliques (mod 2)

I have never come across anything like this in the literature, but it is a fun question. It is reminiscent of the Lights-Out puzzle on general graphs.

Here is a greedy approach that gives $\leq |V(G)|-1$ cliques. Suppose we have some graph $G$ that we want to express as a sum of cliques.

Start with an empty graph $H$ with $V(H)=V(G)$. While $H$ is not isomorphic to $G$, choose a vertex $v$ that has the highest number of "incorrect" (non-)edges, i.e. the highest number of other vertices $w$ such that $vw \in E(H)\triangle E(G)$ (symmetric difference). Add a clique on the set of vertices $\{v\} \cup \{ w |vw \in E(H)\triangle E(G)\}$. Now all of $v$'s edges are "correct", and $v$ will never be chosen again to appear in a clique.

Note that this is not always optimal if the goal is to express as a sum of as few cliques as possible. Take, for example, the bowtie graph (two triangles that share a vertex). The above greedy algorithm uses 3 cliques, when it is easy to see that this graph is expressible as a sum of 2 cliques.


The closest notion to this that I have found in the literature is that of subgraph complementation, introduced by Kamiński, Lozin, and Milanič, in which the edges of a given induced subgraph of a graph $G$ are complemented. Then we may phrase your problem as building $G$ by taking successive subgraph complements, starting with the empty graph on $V(G)$.

In fact, your question inspired a research project amongst myself and the two others who responded to this post, the product of which is available here: arXiv:2101.06180.

We provide upper bounds on the minimum number of cliques in an expression of $G$ as you describe in terms of the number of vertices, the number of edges, and the size of a minimum vertex cover. We relate this problem to the minimum rank problem over the field of order $2$, enabling us in some cases to find the minimum size of such an expression. We also show that, similar to the minimum rank problem over $\mathbb{F}_2$, the class of graphs which may be expressed as a sum of $k$ cliques is hereditary and finitely defined for any positive integer $k$.

By considering an incidence matrix corresponding to a collection of cliques in an expression, we see that your problem is equivalent to that of finding a faithful orthogonal representation of a graph over $\mathbb{F}_2$; that is, an assignment of vectors over $\mathbb{F}_2$ to the vertices of $G$ so that two vectors are orthogonal if and only if they represent non-adjacent vertices. In the study of minimizing the dimension of such a representation, Lozin and Alekseev use an early variant of the subgraph complement (see the proof of Theorem 3).