Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I was wondering if the following decomposition of graphs has been studied, whether it has a name, and what the literature might be on it.

Given a labelled graph G, we decompose its edge-set as a symmetric difference of complete bipartite graphs, where each bipartition may contain any vertices of G that we wish (under the constraint of being disjoint of course), and where each such bipartite graph (each "term" in the decomposition) may be of a different size. We may ask for a "minimal" such decomposition, by different ways of assessing the importance of the "terms": each term has equal weight, or a weight equal to the number of vertices that it contains, and we ask for the decomposition of the smallest total weight.

Has such a decomposition been studied before?

share|cite|improve this question
I found your idea of decomposition very interesting. A similar idea would be to consider just complete graphs instead of bipartite complete graphs. Finally, you should consider posting this question on cstheory Q&A site. Maybe you can have more luck finding an answer there. – Vinicius dos Santos Oct 18 '11 at 22:07
In the case of weighting bipartite graphs by the number of vertices, this problem is equivalent to minimizing the complexity of an expression for quadratic polynomials over $\mathbb F_2$ in the case that there are no linear terms. This was the original motivation for the problem; I thought to ask it independently and without reference to polynomials to see if a fresh viewpoint might bring about answers. – Niel de Beaudrap Oct 28 '11 at 14:51
Can you give a small example? – Felix Goldberg May 25 '12 at 7:59
@FelixGoldberg: Consider the graph $G$ on vertices {a,b,c,d,e,f,g,h} with edge-set {ab,ae,af,ag,ah,be,bf,bg,bh,ce,cf,cg,ch,df,dg,dh}. The edge-set can be decomposed as a symmetric difference of (a) the $K_{4,4}$ graph on the bipartitions {a,b,c,d} and {e,f,g,h}, and (b) the isolated edges (copies of $K_{1,1}$) ab and de. Giving each $K_{m,n}$ term in a decomposition a total weight of $(m+n)$, the decomposition of $G$ consisting of the symmetric "difference" of each edge individually is 32 (twice the number of edges), while the second decomposition is $(4+4) + (1+1) + (1+1) = 12$. – Niel de Beaudrap May 25 '12 at 13:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.