Questions tagged [spanning-tree]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
59 views

Are there digraphs such that any two arborescences are arc-disjoint?

Let $D=(V,A)$ be a directed graph with root $r$. An $r$-arborescence of $D$ is a subgraph such that for any $v\in V-r$, there is exactly one directed path from $r$ to $v$. Hence an $r$-arborescence is ...
9
votes
0answers
154 views

How to sample a lot of independent uniform spanning trees?

There are a bunch of good algorithms for sampling a uniform spanning tree from a graph $G$. For example, Aldous/Broder and Wilson's algorithm are pretty efficient. However, each of these graphs only ...
5
votes
2answers
178 views

Minimising the root-set of a spanning hyperforest of a hypergraph

I am interested in the complexity of a problem involving spanning hyperforests (a union of hypertrees, which covers all of the vertices) of a $k$-hypergraph. I describe the relevant definitions for ...
2
votes
1answer
66 views

Are equally weighted MSTs closely related?

Suppose we have an undirected connected graph $G=(V,E)$ that has several minimum spanning trees. We say two trees $T_1, T_2$ are connected if they share exactly $|V|-2$ edges(*). In other words $T_1$ ...
4
votes
0answers
128 views

Girth of graphs that decompose into two disjoint union of spanning trees

Let $G$ be an $n$-node graph that can be decomposed into two disjoint union of spanning trees. In particular, $G$ has $2n-2$ edges. It is not hard to show that the girth of $G$ is at most $O(\log n)...