The 2-Admissible Property of Graphs in Terms of Radius

Abstract

Let $G$ be a graph and $N_{G}^{2}[D]$ be the 2-closed neighborhood of a vertex subset $D$ in $G$. For a property $\mathcal{P}$ of a graph $G$, a vertex subset $D$ is said to be a \emph{$\mathcal{P}$-2-admissible set} of $G$ if $G-N_{G}^{2}[D]$ admits the property $\mathcal{P}$. The \emph{$\mathcal{P}$-2-admission number} of $G$, denoted by $\eta(G,\,\mathcal{P},\,2)$, is the cardinality of a minimum $\mathcal{P}$-2-admissible set in $G$. We say a graph $G$ has the property $\mathcal{R}_{k}$ if each component of $G$ has radius at most $k$. Then the $\mathcal{R}_{1}$-2-admission number of a graph $G$, denoted by $\eta(G,\,\mathcal{R}_{1},\,2)$, is the cardinality of a minimum
vertex subset $D$ such that $V(G)=N_{G}^{2}[D]$ or each component of $G-N_{G}^{2}[D]$ is a graph having radius at most one. In this paper, we prove that if $G$ is a connected graph of order $n$ such that $G\not\in \{P_{4},\, C_{4},\, C_{9}\}$, then $\eta(G,\,\mathcal{R}_{1},\,2)\leq \frac{n}{5}$, and that the bound is sharp.