John Baptist Gauci
- University of Malta
lunedì 29 aprile 2019
- Mnicourse - 6 lectures
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.