Strong equality of upper domination and independence in trees

Abstract

Let P₁ and P₂ be properties of vertex subsets of a graph G, and assume that every subset of V (G) with property P₂ also has property P₁. Let μ₁(G) and μ₂(G), respectively, denote the maximum cardinalities of sets with properties P₁ and P₂, respectively. Then μ₁(G) ≥ μ₂(G). If μ₁(G) = μ₂(G) and every μ₁(G)-set is also a μ₂(G)-set, then we say μ₁(G) strongly equals μ₂(G), written μ₁(G) ≡ μ₂(G). We provide a constructive characterization of the trees T such that Γ(T) ≡ β(T), where β(T) and Γ(T) are the independence and upper domination numbers of T, respectively.