Seminario: On the Robustness of the Vertex Independence Number of a Forest with respect to Multiple Edge Removals

Contatto di riferimento: Prof. Paolo Toth

Abstract

A vertex subset X of a graph G is an independent set of G if no two vertices in X are adjacent in G. The cardinality of a largest independent set of G is called the (vertex) independence number of G. A nonempty graph G is p-stable if p is the largest number of arbitrary edges of G whose removal from G necessarily results in a graph with independence number equal to that of G, and q-critical if q is the smallest number of arbitrary edges of G whose removal from G necessarily results in a graph with independence number larger than that of G. The classes of p-stable and q-critical forests (acyclic graphs) of order n are characterised in this talk for all admissible combinations of values of p, q and n.