Partial domination - the isolation number of a graph

By Yair Caro, A. Hansberg. 2015

75 citations recorded by the source corpus.

We prove the following result: If $G$ be a connected graph on $n \ge 6$ vertices, then there exists a set of vertices $D$ with $|D| \le \frac{n}{3}$ and such that $V(G) \setminus N[D]$ is an independent set, where $N[D]$ is the closed neighborhood of $D$. Furthermore, the bound is sharp. This seems to be the first result in the direction of partial domination with constrained structure on the graph induced by the non-dominated vertices, which we further elaborate in this paper.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/19f2fb183ef48fcf30042c10e16ad0f2c6f83340