On Perfect Neighborhood and Irredundant Sets in Trees
Xie Ting · Journal of Mathematical Research and Exposition · 2007
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| =■ (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|≤|S| (|S| the cardinality of a maximal irredundant set of T).