Proper Nearly Perfect Sets in Graphs

Abstract

In this paper, we present a new combinatorial problem, called the Nearly Perfect Bipartition Problem, which is motivated by a computer networks application. This leads to a new graph parameter, $P{N}_p(G)$, which equals the maximum cardinality of a proper nearly perfect set. We show that the corresponding decision problem is $NP$-hard, even when restricted to graphs of diameter $3$. We present several bounds for $P{N}_p(G)$ and determine the value of $P{N}_p(G)$ for several classes of graphs.