Completely Independent Spanning Trees And Related Problems Of Graphs

The topological structure of a network can be modeled by a graph.With the expansion of network scale,faults are inevitable.To deal with security problems in information transmission and improve the fault tolerance of the system,constructing the protection route by completely independent spanning trees can provide an alternate transmission path when faults occur randomly,and improving the fault diagnosis abil-ity of system can also reduce the impact of faults on system performance.Therefore,completely independent spanning trees and related problems of graphs are widely used in computer parallel computing,fault-tolerant information transmission,network informa-tion security and so on.In the thesis,the construction method of completely independent spanning trees,sufficient conditions for their existence,and faulty diagnosability in graphs and networks are studied.The thesis is organized as follows:Chapter 1 introduces the research background,significance and research status at home and abroad,and gives the main research results of this thesis.Chapter 2 introduces the definitions,notations and basic lemmas needed in this the-sis.Chapter 3 studies the completely independent spanning trees of S Q_n.The topolog-ical properties of S Q_nare investigated;based on these properties,the existence of two completely independent spanning trees of S Q_nis proved;an algorithm for constructing two completely independent spanning trees of S Q_nis given.Chapter 4 studies the completely independent spanning trees of data center networks D_k,n.It is proved that D_k,ncontains two completely independent spanning trees if k≥0and n≥6,and two completely independent spanning trees of D_k,nare constructed by a recursive method.Chapter 5 gives a sufficient condition for the existence of k completely independent spanning trees in the compound graph G（K_n）and an algorithm for constructing them.As applications of main results,we derived the results that the logical graph of a highly scalable data center network HS DC_m（m）contains two completely independent spanning trees for m≥4,and three completely independent spanning trees for m≥8,and four completely independent spanning trees for m≥10.Chapter 6 proves that the bipartition sufficient condition of Hamiltonian graphs can guarantee the existence of two completely independent spanning trees,and shows that there exists an infinite number of graphs which satisfy this sufficient condition and fail the known sufficient conditions for the existence of two completely independent spanning trees,including Dirac’s condition and Ore’s condition.Chapter 7 studies fault diagnosis of graphs with commonalities by classification.We determine the diagnosability of any graph in two families of graphs M and TN is deter-mined under the PMC and MM^*models respectively with a unique condition on mini-mum degree.As applications of main results,the diagnosability of star graphs,bubble-sort graphs,alternating group networks,data center networks DCell,alternating group graphs etc.under the PMC and MM^*models can be obtained directly.Chapter 8 summarizes the results of this thesis and gives some problems to be further studied.