On the Robustness of the Vertex Independence Number of a Forest with respect to Multiple Edge Removals

Jan Van Vuuren
Stellenbosch University

PDF

Minisymposium: GRAPH DOMINATION

Content: A vertex subset $X\subseteq V$ of a graph $G=(V,E)$ is an {\em independent set} of $G$ if no two vertices in $X$ are adjacent in $G$. The cardinality of a largest independent set of $G$ is called the (vertex) {\em independence number} of $G$. A nonempty graph $G$ is {\em $p$-stable} if $p$ is the largest number of {\em arbitrary} edges of $G$ whose removal from $G$ {\em necessarily} results in a graph with independence number equal to that of $G$, and {\em $q$-critical} if $q$ is the smallest number of {\em arbitrary} edges of $G$ whose removal from $G$ {\em necessarily} results in a graph with independence number larger than that of $G$. The classes of $p$-stable and $q$-critical forests of order $n$ are characterised in this paper for all admissible combinations of values of $p$, $q$ and $n$.

Back to all abstracts