1986/03/01 by Michael S. Jacobson, Lael F. Kinch · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Combinatorics #Mathematics #Vertex (graph theory) #Conjecture #Dominating set #Domination analysis #Graph #Tree (set theory) #Order (exchange) #Discrete mathematics
paper · doi:10.1002/jgt.3190100112
openalex publication_date 1986/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26
Abstract For a graph G , a subset of vertices D is a dominating set if for each vertex X not in D , X is adjacent to at least one vertex of D. The domination number, γ( G ), is the order of the smallest such set. An outstanding conjecture in the theory of domination is for any two graph G and H , One result presented in this paper settles this question in the case when at least one of G or H is a tree. We show that for all graphs G and any tree T. Furthermore, we supply a partial characterization for which pairs of trees, T 1 and T 2 , strict inequality occurs. We show for almost all pairs of trees.