Study On The Decycling Number Of Balanced Hypercubes Network And Kn(?)del Graph

Today's supercomputers include thousands of processors,all of which are large-scale parallel systems.Interconnection network is an important part of supercomputer,which determines the performance of parallel computer to a large extent.How to choose an appropriate and ideal interconnection network topology will become an urgent problem to be solved.All kinds of network topologies have been designed one after another,but how to measure the advantages and disadvantages of these networks?What are the parameters to measure the advantages and disadvantages of network topologies?People hope to find a better way of interconnection by comparing the relevant parameters of these interconnection network topologies,so as to design a better computer system.Loop elimination number,also known as feedback number,is one of the important parameters to measure the performance of network topology.As one of the most classical problems in graph theory,it has been widely used in computer science,interconnection network and communication.It is NP hard to solve the acyclic number of graphs.But up to now,there are few classes of graphs which have given the number of decoys,and even few graphs which have given a better bound of decoys.In particular,some more complex graph classes(including the interconnection network topology with important application prospects)need to be further solved.In this paper,the problem of the number of cycles to be solved is transformed into the problem of constructing the recursive acyclic graph with as many vertices as possible.By using the method of interaction between mathematical construction and computer branch bound search,the mathematical construction is completed through repeated interaction.Finally,the conclusion is proved by mathematical method,and the exact value or tighter bound of the number of cycles to be solved is given.In this paper,equilibrium hypercube networks,knodel graphs,Goldberg snarks and their correlation graphs are studied,and the bounds of their elimination numbers are given.(1)Based on the vertex recurrence structure and edge set property of BHn,the vertex set functions of acyclic graph which can be recursively derived by the method of three separate sets are obtained.Based on these functions,the bounds of the compactness of the acyclic number of Bhn are given[22n-1(1-1/2n-1)+1/2n-1]≤f(BHn)≤22n-22n-1-2n+1(2)By using the cyclic structure of the knodel graph and the designed branch and bound conditions,the construction method of the vertex set of acyclic graph with cyclic section when the degree of the knodel graph is 5 is found.Based on these vertex sets,the bound of the tight acyclic number when the degree of the knodel graph is 5 is given[3n+2/8]≤f(W5,n)≤[3n+6/3](3)According to the composition characteristics of the cyclic structure of Goldberg snarks and its related graphs,the vertex set of acyclic derived subgraphs is constructed,and the exact value of the number of decoys of Goldberg snarks and its related graphs is obtained as follows:f(n)=2n+1...