On potentially Kr1,r2...rm -graphic sequences

Abstract

For given a graph II, a graphic sequence π = (d₁, d ₂,..., d_n) is said to be potentially H-graphic if there exists a realization of π containing H as a subgraph. In this paper, we determine the smallest even integer σ(K_{1s, t}, n) such that each n-term graphic sequence with term sum at least σ(K_{1s, t}, n) is potentially K_{1s, t}-graphic, where n ≥ 3s + 2t²+ 3t - 3 and K_{1s, t} is an r₁ × r₂ × ⋯ × r_s+1 complete a s + 1-partite graph with r ₁ = r₂ = ⋯ = r_s, = 1 and r_s+1 = t. Moreover, we also characterize the potentially K_{r, s}-graphic sequences without zero terms for r = 2, s = 3 and r = 2, s = 4, where K _r,s is an r × s complete bipartite graph.