8
$\begingroup$

Given a graph $G$, define the tree graph $T(G)$ as a graph whose vertices are the spanning trees of $G$, and there is an edge between two trees if one can be obtained from the other by replacing a single edge. That is there is an edge $(T_1, T_2)$ if there exists two edges $x, y \in G$ such that $T_1 - x = T_2 - y$.

My question is this: are there some non-trivial lower or upper bounds on the degree of the vertex with minimum degree in $T(G)$?

Note: I edited the question (last line) a bit to make it less ambiguous .

Improve this question
$\endgroup$
7
  • $\begingroup$ Your definition of an edge doesn't make sense. Do you mean "there is an edge between $T_1$ and $T_2$ if there exists two edges $x, y \in G$ such that $T_1 - x + y = T_2$"? $\endgroup$
    – Tyson Williams
    Commented Sep 25, 2011 at 2:49
  • $\begingroup$ Yes, sorry I meant edges. $\endgroup$
    – corwin
    Commented Sep 25, 2011 at 3:27
  • 3
    $\begingroup$ If $G$ is a tree, its tree graph $T(G)$ is a single vertex with degree 0. On the other hand, if $G$ is a complete graph, every vertex in $T(G)$ has degree $\Theta(n^2)$. What exactly do you mean by "non-trivial"? $\endgroup$
    – Jeffε
    Commented Sep 25, 2011 at 7:30
  • $\begingroup$ it is also clearly greater than the connectivity of $G$ minus 1. Is this trivial? You should expand your question with what you know about the problem already, so that we can judge what you consider trivial and what you don't. $\endgroup$
    – Artem Kaznatcheev ♦
    Commented Sep 25, 2011 at 7:43
  • $\begingroup$ @Jeffe I don't think $\Theta(n^2)$ for a complete graph is correct. Take for example a tree that is a line. Removing an edge from the tree will disconnect the tree into two groups $S$ and $T$. Now there are $|S|\cdot|T|$ edges that can be added to make it a tree again. Taking over all edges of that tree we see that there are $\Theta(n^3)$ nearby trees. $\endgroup$
    – corwin
    Commented Sep 25, 2011 at 13:12

1 Answer 1

Reset to default
12
$\begingroup$

If $G$ has $n$ vertices and $m$ edges, then for any spanning tree $T$ of $G$, each of the $m-n+1$ edges that are not in $T$ may be swapped with any of the edges on the path in $T$ between the endpoints of the non-tree edge. Assuming $G$ is not a multigraph, this gives at least $2(m-n+1)$ different swaps; that is, every $T$ has degree at least $2(m-n+1)$.

This bound is tight: if $G$ has a vertex $v$ adjacent to all others, and $T$ is the spanning tree consisting of all the edges incident to $v$, then the path in $T$ between the endpoints $T$ of every non-tree edge has length exactly two, so each non-tree edge participates in exactly two swaps and $T$ has degree exactly $2(m-n+1)$.

On the other hand if $G$ has girth (shortest cycle length) $g$, then the path in any tree $T$ between the endpoints of any non-tree edge, together with that edge, forms a cycle which must have length at least $g$, so the minimum degree in the tree graph must be at least $(g-1)(m-n+1)$. This bound is tight for some graphs such as the cycle graphs, and complete bipartite graphs, and Moore graphs, since these graphs contain spanning trees for which all non-tree edges induce cycles of length equal to the girth.

However, finding the minimum degree of the tree graph for an arbitrary given graph (equivalently, finding a spanning tree minimizing the sum of lengths of the cycles induced by non-tree edges) is NP-complete: see Deo, Prabhu, and Krishnamoorthy, "Algorithms for Generating Fundamental Cycles in a Graph", ACM TOMS 1982. So finding bounds such as these that are tight for all graphs appears unlikely.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the excellent answer. Can we find a tight upper-bound that is correct for all graphs? $\endgroup$
    – corwin
    Commented Sep 26, 2011 at 0:47
  • $\begingroup$ Also, is there a known upper-bound on the girth of a connected graph with $n$ vertices and $m$ edges? $\endgroup$
    – corwin
    Commented Sep 26, 2011 at 0:52

Your Answer

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

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