Connectivity And Diagnosability Of Leaf-Sort Graphs

In recent years,with the continuing advancements in technology,interconnection networks play an important role in large multiprocessor systems.And with the rapid development of large-scale integration technology,a multiprocessor system may contain hundreds or even thousands of processors.Therefore,the possibility of failure of the system processor increases during the use process.In order to ensure the normal operation of the system,the fault processor must be detected and replaced in time.The identification process is called system diagnosis.In the system diagnosis,the connectivity and diagnosability of the multiprocessor system are two important parameters.The system and interconnection network（networks for short）has a underlying topology,which usually presented by a undirected simple graph G=（V,E）where nodes（vertices）represent processors and links（edges）represent communication links between processors.In order to better study the connectivity and diagnosability of the system,Wang Shiying et al.found and defined leaf-sort graph in 2019.As the latest achievement in the research of new interconnected network topology,leaf-sort graph has good properties such as vertex transfer,recursive structure and high con nectivity.There are few studies on leaf-sort graph.In view of this,this paper focuses on leaf-sort graph for extra connectivity,structure connectivity,substructure connectivity and local diagnosability.This paper is divided into five chapters:In chapter 1,the introduction,we introduce the research background and the main work and conclusion of this paper.In chapter 2,we introduce the definition and properties of leaf-sort graph.In chapter 3,we study the 2-extra connectivity of the leaf-sort graph,and obtain that:（1）When n is odd,the 2-extra connectivity of CF_n is（（9n-9）/2-6）for n≥ 5.（2）When n is even,the 2-extra connectivity of CF_n is（（9n-12）/2-6）for n≥ 6.In chapter 4,we prove structure connectivity and substructure connectivity of the leaf-sort graph by constructing its structure and substructure（only n is odd）,and obtain that:（1）Path P_2k+1,κ(CF_n;P_2k+1)=κ^s(CF_n;P_2k+1)=[（3n-3）/2（k+1）]for n ≥5 and k+1≤（3n-3）/2.（2）Path P_2k,κ(CF_n;P_2k)=κ^s(CF_n;P_2k)=[（3n-3）/2k]for n≥ 5 and k≤（3n-3）/2.（3）Cycle C_2k（there exist only cycles on even vertices in CF_n）,κ(CF_n;C_2k)≥κ^s(CF_n;C_2k)≥[（3n-3）/2k]for n≥5 and k≤（3n-3）/2.In chapter 5,we prove that the leaf-sort graph has the strong local diagnosability property for n≥5,and it keeps this strong property even if there exist（（3n-3）/2-3）missing edges when n is odd and（（3n-4）/2-3）missing edges when n is even in it under the comparison model.