Connectivity parameters of graphs (2 ECTS)

Speaker:  John Baptist Gauci - University of Malta
  Friday, May 10, 2019 at 10:30 AM Mnicourse - 4 lectures
Timetable: Fri 10/5 10:30-12:30, Tue 14/5 10:30-13:30, Thu 16/5 10:30-13:30, Mon 20/5 14:30-16:30 (all lectures in ROOM M)

The property of a graph being connected depends only on whether the graph contains a path for every pair of vertices. However, besides the classical connectivity measures that study the minimum number of vertices or edges that need to be deleted to disconnect the graph, other types of connectivity have recently received much attention. These include connectivity parameters that impose some restrictions on the components of the remaining graph; a notion proposed by Harary (1983) and known as conditional connectivity.

Given a graph G and some graph theoretical property P, the size of the smallest set S of vertices (or edges), if such a set exists, such that the graph G-S is disconnected and every remaining component has property P is the conditional connectivity (or conditional edge-connectivity) of G. Although, theoretically, any property P can be chosen, the most popular choices of P are those having practical applications.

During this course we will mainly focus on maximal connectivity and on certain conditional connectivity parameters of graphs. 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 related results for some families of graphs, including partite graphs, product graphs, circulant graphs, and hypercubes.

Programme Director
Giuseppe Mazzuoccolo

External reference
Publication date
October 1, 2018