Research Seminar: Super-connectivity and super-edge-connectivity of graphs

Network design focuses on determining how to best connect nodes such
that the resulting network is, among other considerations, efficient, resistant
to threats, cost-effective and fault tolerant. A topological optimisation ques-
tion that addresses the requirement of fault-tolerance asks for the connectiv-
ity of the graph (or digraph) underlying the network. Classical connectivity
measures study the minimum number of vertices or edges that need to be
deleted in order to disconnect the graph. Motivated by a question of Harary
in 1983, extensive research has recently been conducted on connectivity pa-
rameters that demand the components of the remaining graph to possess
certain conditions.
In this talk we restrict our attention to the super-connectivity and the
super-edge-connectivity of a graph. These notions respectively study the
least number of vertices and edges that need to be deleted from a graph
to disconnect the graph such that each remaining component is not triv-
ial. In other words, the property that each component must possess is
that of not being an isolated vertex, or equivalently, that of containing at
least one edge. We will present well-known bounds for these parameters
and discuss sufficient conditions for the bounds to be attained in terms of
vertex-degrees, diameter and girth. Finally we review the super-connectivity
and the super-edge-connectivity of some families of graphs, including circu-
lant graphs, hypercubes, generalized Petersen graphs, Kneser graphs and
Johnson graphs.