Generalised independent minimum t-degree

Abstract

Let G be a connected graph on n vertices. Let β₀(G) denote the cardinality of a largest independent set of vertices in G. For 1 ≤ t ≤ β₀(G), the generalised independent minimum t-degree, δ_tⁱ(G), is defined as follows: δ_tⁱ(G) = min{|N(S)|: S is an independent set with t vertices}. We show that for any graph G, β₀(G)+δ_tⁱ(G) ≤ n for all t, 1 ≤ t ≤ β₀(G). Furthermore, we present necessary and sufficient conditions for certain classes of graphs to achieve β₀(G) + δ_tⁱ(G) = n.