Study On The Independent Number Of Important Graphs

In graph theory,the independent number of graphs is an important graph parameter.The study of independent numbers has important applications in predicting new compounds and synthesizing new drugs.We mainly study the independent number problems of two special classes of graphs,namely ladder and antiprism.In the ladder,we mainly studied the generalized ladder,Mobius ladder and circular ladder.For the graphs of antiprism,we mainly study the antiprism An,Rn and Qn.We also give a general algorithm for solving the class independent number problem.For ladders,I get the exact value of the independent number of the generalized trapezoid,Mobius and cyclic trapezoidal graphs,and the exact calculation formula of the sum of three kinds of independent sets of graphs is obtained.I use the idea of transformation matrix to set up the program to verify the result.For the graphs of antiprism,we mainly study three kinds of antiprism graphs,namely the antiprism An,Rn and Qn.We find out the independent numbers of three classes of graphs and find out the exact formulas for the sum of independent sets of antiprism classes.Because the classes and structures of the antiprisms are more complex and general,we are very difficult to calculate the exact formula,so we give their upper or lower bounds.For any graph,we give a general algorithm.The problem of any graph can be calculated.It is verified by two graphs and parts.Select two special drawings,such as K5,4,3,2 and K5,4,3,2,4.The results are in good agreement with those calculated by the general formula.However,the application of general algorithm still has some limitations.It is believed that with the rapid development of computer networks,this problem will no longer be a problem,and will greatly promote the study of independent number problems of important graphs.