2
$\begingroup$

This is in the same spirit as this stackexchange post, but I am seeking a more general answer.

The goal is, given a graph $G$, give a method of counting the minimum number of spanning trees needed (labeled $T_1, \dots, T_n$) such that $\forall e \in E(G) \, , \exists i \in \{1, \dots, n\} \, s.t. \, e \in T_i$.

I am trying to find any results in this vein, but haven't had much luck. So far, I can prove that for cycles and complete graphs, the solutions are $2$ and $\lceil \frac{n}{2} \rceil$ respectively. Also, I know that for complete bipartite graphs $K_{m,n}$, where $m \leq n$, the answer to this question is $m$. These seem rather basic, however, and I am seeking some harder questions to answer.

$\endgroup$
  • $\begingroup$ I doubt there's a closed form solution. Are there specific classes of graphs you're interested in? $\endgroup$ – TokenToucan May 22 '15 at 3:51
  • 1
    $\begingroup$ The question is about finding questions. You could try to find an algorithm for specific classes. For instance, is there a method that applies to all bipartite graphs ? Is the general problem NP-Hard (I'd think so) ? If you're not into algorithms, you could try to find bounds for specific classes. Can you bound the number of trees required for, say, planar graphs ? Or is it unbounded ? Try other popular classes. What about the min/max degree ? How do they relate to the number of trees ? $\endgroup$ – Manuel Lafond May 22 '15 at 3:54
  • $\begingroup$ @CuddlyCuttlefish I think bipartite graphs are what I'm after for practical purposes. However, I need to verify that what I'm thinking of would actually be bipartite (I am less convinced of this than I initially thought). $\endgroup$ – Robert Short May 23 '15 at 2:10
  • $\begingroup$ @ManuelLafond These are great questions! I have looked into bipartite graphs. I was wondering if there was a phrase for this problem in general that may/may not apply. Something that I could google and find results would be supremely helpful. I've thought a bit about planar graphs, if only because the characterization falls neatly out of what I've already looked at. The issue is whether this number for a graph is necessarily greater than or equal to this property for a minor, but then it follows from what I have that non-planar graphs require at least 3 trees to cover all edges. $\endgroup$ – Robert Short May 23 '15 at 2:13
2
$\begingroup$

A bit of a late answer, but I think it's interesting.

There's this thing called the graph arboricity : See here.

It's the minimum number of edge-disjoint forests needed to cover every edge exactly once. It's actually equivalent to the number of spanning trees needed to cover every edge (with possible repetitions). We have to assume that the graph is connected.

To see this, a set of forests can easily be transformed into a set of spanning trees (by adding edges to connect forest components together). Conversely, a set of spanning can be transformed into a set of forests by removing the edges that are covered more than once.

According to the wiki page, the number you're looking for is $max \{e_S / (n_S - 1) : S \subseteq V(G) \}$, where $n_S = |S|$ and $e_S$ is the number of edges in the subgraph induced by $S$. That is, find the subgraph with the densest edge to vertices ratio.

There's a polynomial time algorithm mentioned on the wiki page, though it doesn't look trivial.

$\endgroup$
  • $\begingroup$ This is perfect. Exactly what I was looking for. Thanks Manuel! $\endgroup$ – Robert Short May 29 '15 at 13:13

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.