Studies On Properties Of Degree Sequences Of Graphs

Let G=(V,E)be a finite simple undirected graph with the vertex set V and the edge set E.The degree of a vertex x ? V is the number of vertices adjacent to x,denoted by degG(x).Given a graph G of order n,let G[i]denote the subgraph induced by the set of vertices a having deg(u)=i,for 0 ?i ?n-1.We call G[i]a degree graph.In particular,when G is a tree,G[i]is called a degree forest.Given a graph G of order n,let the degrees of each vertices be a sequence with non increasing order.We say that sequence is degree sequence,denoted by d(G).If there is a sequence d with non increasing order that is a degree sequence of some graph G,then we say that d is graphic sequence and G is the realization of d.First,we give the necessary and sufficient conditions for the 3-partite graphic sequences.Then,we study the graphics of degree graphs based on the induction of the number of non-empty degree graphs,we give the necessary and sufficient conditions for the number of non-empty degree graphs to be 1,2,3 and k re-spectively.And we give a sufficient condition of graphics of degree forests,when there are enough leaves,that is,n1=?i=2n-1(ini-Si)-2(?i=2n-1 li-1),where G1 represents the number of vertices in the subset V1.Finally,we give some results about the properties of vertex classification according to different standards.One is according to the size relationship between degree and average degree,denoted by GAVG+,GAVG,GAVG-,the other is according to the size relationship be-tween the number of vertices whose degree is greater than the given vertex and the number of vertices whose degree is less than the given vertex,denoted by MED,MAJ,MIN.