A characterization for a graphic sequence to be potentially K 2,s-graphic

Abstract

A non-increasing sequence π = (d₁, d₂,...,d _n, of nonnegative integers is said to be potentially K _r,s-graphic if it is realizable by a graph on n vertices containing K_r,s as a subgraph, where K_r,s is the r × s complete bipartite graph. In this paper, we characterize the potentially K _2,s-graphic sequences. This characterization partially answers one problem due to Li and Yin (Adv. Math., 33(2004), 273-283).