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

The k -residue of a graph, introduced by Jelen in a 1999 paper, is a lower bound on the k -independence number for every positive integer k . 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 k , the k -residue of disjoint unions is at most the sum of the k -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 k -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 k -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 k -residue, further motivating our first application of the lemma.