The Criteria Of Graphic Sequences

Graphic sequences theory plays a very important role in Graph theory, and thereare lots of perfect theories of the criteria for sequences being graphic. In this paper, anew conception of quasigraphic sequences is introduced, and from the view ofquasigraphic sequences the criteria for quasigraphic sequences being graphic arestudied. At the same time, the related properties of quasigraphic sequences are studiedby partition-listing technique. In addition, the criteria for a special kind of integersequences being graphic and generalizations of a criterion for integer sequences beinggraphic are obtained.The main results of the thesis can be summarized as follows: Firstly, theconception of quasigraphic sequences is given and a partition-listing technique whichcan be used to list all quasigraphic sequences with fixed sum2nis introduced.Secondly some criteria for judging whether the quasigraphic sequences are graphicare obtained by the existing criteria and the partition-listing technique. Then therelation of the number of quasigraphic sequences with different sum is given, and themethod of constructing all quasigraphic sequences with sum2(n1)from thequasigraphic sequences with sum2nbased on the listing technique is obtained. It isworth noting that this method keep the immutability of graphic sequences, that is, thesequences with sum2(n1)obtained from the graphic sequences with sum2nbythis method are all graphic. Finally, the criteria for a special kind of integer sequences(G (2,k)graphic sequences) being graphic and generalizations of a criterion forinteger sequences being graphic are obtained.