Two sufficient conditions for a graphic sequence to have a realization with prescribed clique size Original Research Article

A graphic sequence image is said to be potentially image-graphic, if image has a realization G containing image, a clique of image vertices, as a subgraph. In this paper, we give two simple sufficient conditions for a graphic sequence image to be potentially image-graphic. We also show that the two sufficient conditions imply a theorem due to Rao [An Erdös-Gallai type result on the clique number of a realization of a degree sequence unpublished.], a theorem due to Li et al [The Erdös–Jacobson–Lehel conjecture on potentially image-graphic sequences is true, Sci. China Ser. A 41 (1998) 510–520.], the Erdös–Jacobson–Lehel conjecture on image which was confirmed (see [Potentially image-graphical degree sequences, in: Y. Alavi et al. (Eds.), Combinatorics, Graph Theory, and Algorithms, vol. 1, New Issues Press, Kalamazoo Michigan, 1999, pp. 451–460; The smallest degree sum that yields potentially image-graphic sequences, J. Graph Theory 29 (1998) 63–72; An extremal problem on the potentially image-graphic sequence, Discrete Math. 212 (2000) 223–231; The Erdös–Jacobson–Lehel conjecture on potentially image-graphic sequences is true, Sci. China Ser. A 41 (1998) 510–520.]) and the Yin–Li–Mao conjecture on image [An extremal problem on the potentially image-graphic sequences, Ars Combin. 74 (2005) 151–159.], where image is a graph obtained by deleting one edge from image.