Fault tolerance in rose window graphs

Interconnection networks are one of the basic components of parallel processing and distributed systems and are becoming more and more important with the development of technology. The preferred interconnection network topology in a system plays a decisive role in the overall performance. An efficient topology that enables fast and high-quality data communication between remote processors usually has a high level of fault tolerance. Therefore, assessing the fault tolerance of interconnection networks is critical to improve the reliability of the system. One of the most basic metrics used in this assessment is connectivity. However, most connectivity parameters consider a single vertex failure and ignore the structural failures of the network. In 2016, Lin et al. introduced the concepts of structure and substructure connectivity, which provide a more comprehensive framework for assessing the fault tolerance of the network. Let H be a subgraph of connected graph G and F be a set of subgraphs of G. F is a H-structure cut of G if every element of F is isomorphic to H (resp. isomorphic to a connected subgraph of H) when G-F is disconnected or is an isolated vertex. The H -structure connectivity (respectively, H substructure connectivity) of G is the minimum cardinality of overall H -structure cuts (resp. H -substructure cuts). This thesis investigates the fault tolerance of the edge-transitive rose window graph, a 4-regular graph family, by analysing its structure connectivity and substructure connectivity.