I will call two graphs $G$ and $H$, $r$-equidecomposable (in analogy with Hilbert's third problem) if they can be written as unions of disjoint subgraphs $$G\cong \bigsqcup_{i=1}^r G_i\quad ,\quad H\cong \bigsqcup_{i=1}^r H_i$$ (disjoint here means they have no common edges), and $G_i\cong H_i $ for $1\le i \le r$. Let $\epsilon(G,H)$ be the smallest $r$ for which $G$ and $H$ are $r$-equidecomposable. Let $$f(n,m)=\max_{G,H\in V(n,m) } \epsilon(G,H) $$ where $V(n,m)$ is the collection of all graphs with $n$ vertices and $m$ edges.

Is the sequence $f(n,m)$ unimodal for fixed $n$? Can one find asymptotics for values such as $f\left(n,\frac{n(n-1)}{4}\right)$ when $n$ is large?

  • $\begingroup$ This looks like a very mean packing problem. $\endgroup$ – Felix Goldberg May 10 '12 at 21:02
  • $\begingroup$ I'm having trouble visualizing examples where epsilon > n/2. Are there any? Gerhard "Ask Me About System Design" Paseman, 2012.05.10 $\endgroup$ – Gerhard Paseman May 11 '12 at 0:58
  • $\begingroup$ Gerhard, think of disjoint triangles versus a bipartite graph with the same number of edges. $\endgroup$ – Gjergji Zaimi May 11 '12 at 4:56
  • $\begingroup$ OK, I can improve on n/2 with your suggestion. All my high scorers involve star graphs. Do you know of other examples not using star graphs? Also, it feels like one should get an upper bound of O(n) for f using degree sequences. What upper bounds do you know? Gerhard "Ask Me About System Design" Paseman, 2012.05.11 $\endgroup$ – Gerhard Paseman May 11 '12 at 15:42
  • 1
    $\begingroup$ While we wait for Gjergji to respond, let me suggest the following examples on n=6k+4 vertices. The first is a star graph on n/2 vertices paired with (n/2 - 1) disjoint copies of K_2; this has r=n/2 - 1 . The second has 2k+1 disjoint triangles paired with a star graph on n vertices. This has r= 2n/3. I know of no smaller r for either of these examples. Gerhard "Ask Me About System Design" Paseman, 2012.05.11 $\endgroup$ – Gerhard Paseman May 12 '12 at 5:06

If Joseph is going to take this as an opportunity to show some nice and illustrative pictures, I am going to do similarly, but using words instead. Gjergji probably already knows what I am going to say, but others might find the remarks a useful stepping stone to the subject.

My initial thought was using a star graph, which on m nodes has a degree sequence of (m-1) 1's and 1 entry of (m-1). Embedding this into n=2m nodes and choosing H to be a graph of m disconnected edges gives that n/2 is a lower bound for f(n,n/2) and n even, and an analogous bound for n odd. Gjergji hints at a better construction in the comments which asymptotically gives a lower bound of 2n/3 .

It so happens that every graph on n nodes is r-decomposable into star graphs for some r less than n. A nice argument on degree sequences allows one to remove a star graph from each of G and H leaving at least one vertex in one of the graphs with no edges, and then a second star graph can be removed from each to guarantee that a vertex in the other graph has no edges. This allows us to look at the situation on n-1 nodes and gives an upper bound of 2n (which can be tightened to 2n-6 for n>3) for f(n,m) for any m.

If there is a relation between decomposability for a pair of graphs and decomposability for their complements, I have not found it yet. However having min (m, floor(2n/3)) and 2n as upper and lower bounds on parts of f suggests to me that f is unimodal, that there are nice asymptotics and that for m between n and ((n choose 2) - n), the asymptotic value for f(n,m) will be Cn for some constant C less than 2, most likely C=1.

Using star graphs for the pieces provides nice results. It might be good to consider decomposition into certain graph classes like paths or trees and see what asymptotics can be found using such restrictions.

Gerhard "Ask Me About System Design" Paseman, 2012.05.11


Not an answer (cool question!), just an excuse to show a pair of 2-equidecomposable graphs, one planar, one not:
          Petersen Graph

  • $\begingroup$ Nice! Did you use Mathematica? $\endgroup$ – Felix Goldberg May 10 '12 at 15:33
  • $\begingroup$ @Felix: Adobe Illustrator. :-) $\endgroup$ – Joseph O'Rourke May 10 '12 at 15:35

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.