6
$\begingroup$

The definition of resilience with a graph $G$ w.r.t to a monotone property $\mathcal{P}$ is well known.

(Global resilience) Let $\mathcal{P}$ be an increasing monotone property. The global resilience of $G$ with respect to $\mathcal{P}$ is the minimum number $r$ such that by deleting $r$ edges from $G$ one can obtain a graph not having $\mathcal{P}$.

(Local resilience) Given a monotone increasing property $\mathcal{P}$. The local resilience of a graph $G$ with respect to $\mathcal{P}$ is the minimum number $r$ such that by deleting at each vertex of $G$ at most $r$ edges one can obtain a graph not having $P$.

A fair bit of work has been done in a random graph setting. I was wondering if perhaps given an arbitrary graph are there are algorithms for computing it's resilience w.r.t some property $\mathcal{P}$?

$\endgroup$
0

0

Your Answer

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