Connectivity parameters of the hypercube graph and its variants

Abstract

Classical connectivity (edge-connectivity) measures study the minimum number of vertices (or edges) that need to be deleted to disconnect a graph. A network is more fault-tolerant if the number of vertices (or edges) that need to be deleted to disconnect the graph is high. In this dissertation we will focus on the deletion of vertices in order to disconnect graphs. A vertex cut S of a graph G is a set of vertices of G whose deletion results in a disconnected graph or leaves an isolated vertex. The minimum size over all vertex cuts of G is the connectivity κ(G) of the graph G. Many have argued that the connectivity of a graph does not necessarily measure in an accurate way how fault-tolerant a graph would be following the deletion of a set of vertices. This is because it assumes that all the vertices adjacent to any vertex of the graph can fail simultaneously, a particularly remote instance in large–scale processing systems. Thus, other types of connectivity parameters that impose some restrictions on the components of the remaining graph have recently received much attention; a notion proposed by Harary in 1983. Given a graph G and some graph theoretical property P, the size of the smallest set S of vertices, if such a set exists, such that the graph G − S is disconnected and every remaining component has property P is the conditional connectivity of G. Although, theoretically, any property P can be chosen, the most popular choices of P are those having practical applications. One such property that can be chosen is that each of the remaining components has more than h vertices, for some positive integer h. This notion is known as the h–extraconnectivity κh(G) of a graph G. Thus, for h = 0, we have κh(G) = κ(G). Harary proposed the study of the conditional connectivity of some interesting families of graphs, such as complete multipartite graphs, the generalized Petersen graphs and the hypercube graphs. The latter family provides, in fact, a fundamental model for computer networks and these graphs have been extensively used due to their various properties, such as regularity and recursive structure. For any positive integer n, the n-dimensional hypercube is a graph Qn whose vertex set is made up of all possible n-bit binary strings, and two vertices are connected by an edge whenever their binary string representation differs in only one bit position. Thus, Qn has 2n vertices and n2n−1 edges, is regular of degree n and has connectivity equal to n. A number of variants of the n-dimensional hypercubes have been introduced with the aim of further enhancing their properties. Various basic graph-theoretic parameters have been established for these new hypercubes, including the girth, diameter and connectivity. In this dissertation we survey the existing literature on the connectivity and the h-extraconnectivity of hypercube graphs, starting from the work of Yang and Meng on the (standard) n-dimensional hypercube, and proceeding to a number of hypercube variants. The aim of this research is to present and analyse the main results on these two connectivity parameters, and to establish the values of h for which κh is known.