8
$\begingroup$

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?

$\endgroup$
4
  • 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$ Oct 18, 2011 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$ Oct 28, 2011 at 14:51
  • $\begingroup$ Can you give a small example? $\endgroup$ May 25, 2012 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$ May 25, 2012 at 13:51

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.