![]() ![]() 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.The first matches of the World cup have been played! 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. Various basic graph-theoretic parameters have been established for these new hypercubes, including the girth, diameter and connectivity. A number of variants of the n-dimensional hypercubes have been introduced with the aim of further enhancing their properties. Thus, Qn has 2n vertices and n2n−1 edges, is regular of degree n and has connectivity equal to n. 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. 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. 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. This notion is known as the h–extraconnectivity κh(G) of a graph G. One such property that can be chosen is that each of the remaining components has more than h vertices, for some positive integer h. Although, theoretically, any property P can be chosen, the most popular choices of P are those having practical applications. 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. 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. 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. 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. ![]() The minimum size over all vertex cuts of G is the connectivity κ(G) of the graph G. 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. In this dissertation we will focus on the deletion of vertices in order to disconnect graphs. A network is more fault-tolerant if the number of vertices (or edges) that need to be deleted to disconnect the graph is high. Connectivity parameters of the hypercube graph and its variants (Master's dissertation).Ĭlassical connectivity (edge-connectivity) measures study the minimum number of vertices (or edges) that need to be deleted to disconnect a graph. Please use this identifier to cite or link to this item:Ĭonnectivity parameters of the hypercube graph and its variants
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |