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 ?
1

$\begingroup$ I guess you mean "minimum feedback vertex set", etc. $\endgroup$ – Brendan McKay May 6 '15 at 2:32
4
$\begingroup$
$\endgroup$
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/21)n$ edges, which in turn implies we must remove $(1/21/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