On maximizing private neighbors in graphs

Abstract

Given a set $U\subset V$ of vertices in a graph $G=(V,E)$, a {\it private neighbor with respect to the set $U$} is any vertex $w\in V$ having precisely one neighbor, say $v$, in $U$. If $w\in V-U$, then $w$ is called an {\it external private neighbor} of $v$ with respect to $U$. If $w\in U$ then $w$ is called an {\it internal private neighbor} of $v$ with respect to $U$. We also add one special case: if $w\in U$ and $N(w)\cap U=\varnothing$, then we say that $w$ is a {\it self private neighbor} with respect to $U$. By definition, a self private neighbor with respect to $U$ is an isolated vertex in the subgraph of $G$ induced by $U$. In this paper we consider the general problems of trying to find sets of vertices which maximize the number of private neighbors of specific types in a graph. In the process of doing this we define several new maximization parameters of graphs which generalize some known and well-studied parameters of graphs relating to vertex and edge independence, domination and irredundance in graphs.

17 pages, 3 figures