On Perfect Neighborhood and Irredundant Sets in Trees

Abstract:

      For any tree $T$, we give an Algorithm (A) with polynomial time complexity to get the perfect neighborhood set in $T$. Then we prove that $S$, which is a perfect neighborhood set of $T$ and $|S|=\Theta (T)$, is also a maximal irredundant set in $T$. We present an Algorithm~(B) with polynomial time complexity to form the perfect neighborhood set from the maximal irredundant set in $T$, and point out that $T$ has an independent perfect neighborhood set $U$ and $|U|\le |S|~(|S|$ the cardinality of a maximal irredundant set of $T)$.