On the kk-residue of disjoint unions of graphs with applications to kk-independence

The kk-residue of a graph, introduced by Jelen in a 1999 paper, is a lower bound on the kk-independence number for every positive integer kk. This generalized earlier work by Favaron, Mahéo, and Saclé, by Griggs and Kleitman, and also by Triesch, who all showed that the independence number of a graph is at least as large as its Havel–Hakimi residue, defined by Fajtlowicz. We show here that, for every positive integer kk, the kk-residue of disjoint unions is at most the sum of the kk-residues of the connected components considered separately, and give applications of this lemma. Our main application is an improvement on Jelen’s bound for connected graphs which have a maximum degree cut-vertex. We demonstrate constructively that, in some cases, our extensions give better approximations to the kk-independence number than all known lower bounds—including bounds of Hopkins and Staton, Caro and Tuza, Favaron, Caro and Hansberg, as well as Jelen’s kk-residue bound itself. Additionally, we apply this disjoint union lemma to prove a theorem for function graphs (those graphs formed by connecting vertices from a graph and its copy according to a given function) while simultaneously giving, in this context, different classes of non-trivial examples for which our new results improve on the kk-residue, further motivating our first application of the lemma.