Go to the University of Bologna homepage
Department of Electrical, Electronic, and Information Engineering "Guglielmo Marconi" - DEI

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

The seminar will be given by Jan van Vuuren, Professor, Department of Industrial Engineering, Stellenbosch University, South Africa.

  • Date: 30 June 2016

  • Event location: Room 5.5, School of Engineering and Architecture, viale Risorgimento 2, Bologna

Contact Name:

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.