Is the feedback vertex number bounded by the maximum number of leaves in a spanning tree?

Question

I have a graph-theoretical conjecture which I think would have been studied before, but for which I cannot find anything in the literature.

Let G be a finite, simple, connected graph. Let the feedback vertex number $FVS(G)$ be the minimum number of vertices that have to be deleted from $G$ to break all cycles, so the minimum number of deletions needed to turn $G$ into a forest. Let the max leaf number $MaxLeaf(G)$ be the maximum number of leaves in any spanning tree for $G$.

My conjecture is that $FVS(G) \leq MaxLeaf(G)$.

The two numbers come close for complete graphs: a $K_t$ has a spanning tree with $(t-1)$ leaves, and $(t-2)$ deletions are needed to turn $K_t$ into a forest. Since a forest can have an arbitrary number of leaves and has FVS number 0, the MaxLeaf number cannot be bounded by a function of the FVS number.

I can prove that $FVS(G) \leq 6 \cdot MaxLeaf(G)$ through a lemma on spanning trees which says that for every connected graph G containing m vertices of degree $\neq 2$, there is a spanning tree for G with at least $m/6$ leaves. Since the deletion of the set of vertices of degree $\neq 2$ turns a graph into a forest if the graph is not a simple cycle, this shows that $FVS(G) \leq 6 \cdot MaxLeaf(G)$ when $G$ is not a simple cycle; and it is easy to see that the claim also holds when $G$ is a simple cycle since $MaxLeaf(C_n) = 2$ and $FVS(C_n) = 1$ for $n \geq 3$.

Since the complement of the leaves in a spanning tree form a connected dominating set, and since the complement of a feedback vertex set is a maximum induced forest, an alternative way to state the conjecture is: For any connected graph $G$ the number of vertices in the largest induced subforest of $G$ is at least as large as the minimum size of a connected dominating set in $G$.

So my question is: is this conjecture true, and does anyone know of any research related to it?

Answer 1

Bill Waller and I proved the stronger statement that for G a graph on n(G) > 1 vertices, the order of a largest induced linear forest is at least one plus the connected domination number. See our preprint. A linear forest is a forest in which each connected component is a path, and clearly a lower bound for the order of a largest forest.

Answer 2

This isn't a complete answer, but at least it's a step. I think it should be possible to prove that FVS(G) < 2 MaxLeaf(G).

More specifically, if NonTwo(T) is the number of nodes in spanning tree T that do not have degree two, and MaxNonTwo(G) is the maximum value of NonTwo(T) over all spanning trees of G, then I think that

• MaxNonTwo(G) < 2 MaxLeaf(G). This is obvious: in any tree, the number of leaves in T is greater than half of NonTwo(T), so the tree T that maximizes NonTwo(T) has greater than NonTwo(T)/2 leaves, and the max leaf spanning tree can only have even more leaves.

• FVS(G) ≤ MaxNonTwo(G). More specifically, in every tree T maximizing NonTwo(T), the set of vertices of degree ≠ 2 form a feedback vertex set. For, if there's a cycle induced by the degree-2 vertices of T, then some edge e of the cycle does not belong to T. If the path in T connecting the endpoints of e passes through a vertex v that does not have degree three, then adding e and removing an edge incident to v produces a tree with a larger value of NonTwo(T). If this situation does not occur, then all edges in the induced cycle are non-tree edges; adding two consecutive edges from the cycle to T and removing two of the edges from T (two of the three edges at the median in T of the endpoints of the added cycle edges) produces a new tree with greater NonTwo again (the three endpoints of the added edges get their degree increased above two, the median goes from degree three to degree one, and two other vertices get their degrees decreased from three to two).