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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Vinicius dos Santos Oct 18 '11 at 22:07
  • 2
    $\begingroup$ 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. $\endgroup$ – Niel de Beaudrap Oct 28 '11 at 14:51
  • $\begingroup$ Can you give a small example? $\endgroup$ – Felix Goldberg May 25 '12 at 7:59
  • $\begingroup$ @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$. $\endgroup$ – Niel de Beaudrap May 25 '12 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.