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$
$\endgroup$
1
-
$\begingroup$ I guess you mean "minimum feedback vertex set", etc. $\endgroup$– Brendan McKayCommented May 6, 2015 at 2:32
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$ Commented May 19, 2015 at 1:53
-
$\begingroup$ Very elegant! Thanks for pointing this out :-) $\endgroup$ Commented May 20, 2015 at 5:01