Feedback vertex set is a set of vertices whose removal leaves an acyclic graph. It is known that every vertex transitive graph on $n$ vertices has minimum vertex cover of size $\Omega(n)$. It is also not difficult to show that every connected vertex transitive graph (except for the cycle of length $n$) has minimum feedback vertex set of size $\Omega(n/\log^2 n)$. Does $\Omega(n)$ bound hold for the same ?

  • $\begingroup$ I guess you mean "minimum feedback vertex set", etc. $\endgroup$ – Brendan McKay May 6 '15 at 2:32

Let $d \ge 3$ be the degree of the graph. Then the graph has $dn/2$ edges. In order to make it acyclic we must remove at least $(d/2-1)n$ edges, which in turn implies we must remove $(1/2-1/d)n = \Omega(n)$ vertices. Notice that it suffices to assume the graph is $d$ regular, we don't need transitivity.

  • $\begingroup$ Note also that this is $\Omega(n)$ only if $d>2$; but if $d=2$, then (assuming connectedness) we are in the cycle case that was excluded. (Indeed, it seems that otherwise, not only do you not need transitivity, you don't even need connectedness.) $\endgroup$ – Harry Altman May 19 '15 at 1:53
  • $\begingroup$ Very elegant! Thanks for pointing this out :-) $\endgroup$ – Raghav Kulkarni May 20 '15 at 5:01

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.