POTENTIALLY GRAPHIC SEQUENCES OF SPLIT GRAPHS

A sequence pi = (d(1), d(2) , . . . , d(n)) of non-negative integers is said to be graphic if it is the degree sequence of a simple G on n vertices, and such a graph G is referred to as a realization of pi. These to fall non-increasing non-negative integer sequences pi = (d(1), d(2), . . . , d(n)) is denoted by NSn. A sequence pi is an element of NSn is said to be graphic if it is the degree sequence of a graph G on n vertices, and such a graph G is called a realization of pi. The set of all graphic sequences in NSn is denoted by GS(n). A split graph K-r + (K-s) over bar on r + s vertices is denoted by S-r,S-s. A graphic sequence pi is potentially H-graphic if there is a realizaton of pi containing H as a sub graph . In this paper, we determine the graphic sequences of subgraphs H, where H is S-r1,S-s1 + S-r2,S-s2 + S-r3,S-s3 + . . . + S-rm,S-sm, S-r1,S-s1 boolean OR S-r2,S-s2 boolean OR . . . boolean OR S-rm,S-sm and S-r1,(s1) x S-r2,S-s2 x . . . x S(rm,)s(m) and +, V and x denotes the standard join operation, the normal join operation and the cartesian product in these graphs respectively.