Connectivity in product graphs

Abstract

A quick and intuitive way how new mathematical objects can be built from smaller ones employs the notion of products. In graph theory, two main products that are widely studied because they exploit the structure of their factors in a meaningful way are the Cartesian product and the direct product. Connectivity parameters can be and have been studied on graph products, leading to many interesting and at times surprising results. For instance, whereas the Cartesian product of two graphs is connected if and only if one of its factors is connected, the direct product of two connected graphs is connected if and only if at most one of the factors is bipartite. Apart from the classical vertex-and-edge connectivity, other parameters can be employed to determine how connected a graph is, in particular the super-connectivity of a graph. The aim of this project is to find, collate, review and analyse the main results on connectivity and super-connectivity of product graphs.