Strong Equality of Upper Domination and Independence in Trees

Document Type


Publication Date



Let P1 and P2 be properties of vertex subsets of a graph G, and assume that every subset of V (G) with property P2 also has property P1. Let μ1(G) and μ2(G), respectively, denote the maximum cardinalities of sets with properties P1 and P2, respectively. Then μ1(G) ≥ μ2(G). If μ1(G) = μ2(G) and every μ1(G)-set is also a μ2(G)-set, then we say μ1(G) strongly equals μ2(G), written μ1(G) ≡ μ2(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.

This document is currently not available here.