Bounds on the Upper k-Domination Number and the Upper k-Star-Forming Number of a Graph

摘要

A subset A of vertices of a graph G is a κ-dominating set if every vertex not in A has at least k neighbors in A and a κ-star-forming set if every vertex not in A forms with k vertices of A a not necessarily induced star K_1,k- The maximum cardinalities of a minimal k-dominating set and of a minimal fc-star-forming set of G are respectively denoted by Γ_κ(G) and SF_κ(G).We determine upper bounds on Γ_κ(G) and SF_κ(G) and describe the structure of the extremal graphs attaining them.