Potentially Km-G-graphical sequences: A survey

The set of all non-increasing nonnegative integer sequences pi = (d(v (1)), d(v (2)), aEuro broken vertical bar, d(v (n) )) is denoted by NS (n) . A sequence pi a NS (n) is said to be graphic if it is the degree sequence of a simple graph G on n vertices, and such a graph G is called a realization of pi. The set of all graphic sequences in NS (n) is denoted by GS (n) . A graphical sequence pi is potentially H-graphical if there is a realization of pi containing H as a subgraph, while pi is forcibly H-graphical if every realization of pi contains H as a subgraph. Let K (k) denote a complete graph on k vertices. Let K (m) -H be the graph obtained from Km by removing the edges set E(H) of the graph H (H is a subgraph of K (m) ). This paper summarizes briefly some recent results on potentially K (m) -G-graphic sequences and give a useful classification for determining sigma (H, n).