4
$\begingroup$

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)$. However, I don't have an example with girth bigger than $4$.

Do we have an example of such graph whose girth is $\Theta(\log n)$, or is there a way to prove an even better upper bound?

I wonder if there are constant degree expanders that, after removing an appropriate number of edges, can be decomposed into two disjoint union of spanning trees.

$\endgroup$
  • 1
    $\begingroup$ Not sure if this can be generalized, but here is a graph on $\mathbb{Z}/2n\mathbb{Z}$ with girth $6$, where $(x,y)\in E$ iff $x-y$ has the following values: $\pm 1$, or $\pm 2p$ when $x$ is even, or $\pm 2q$ when $x$ is odd. Here $p,q,n$ are coprime and $1<p<q-1$. The graph can be decomposed into two Hamiltonian paths with two extra edges. $\endgroup$ – Willard Zhan Oct 25 '17 at 22:23
  • $\begingroup$ The following paper on two random spanning trees giving an expander may be helpful in answering your question. arxiv.org/abs/0807.1496 $\endgroup$ – Chandra Chekuri Oct 26 '17 at 23:47

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.