The smallest degree sum that yields potentially K r1,r2,...,rl,2,s-graphic sequences

Abstract

Let σ(K_{r1,r2,...,re,r,s,} n) be the smallest even integer such that every n-term graphic sequence π = (d₁, d₂ , d_n) with term sum σ(π) = d₁ + d₂ + ... + d_n ≥ σ(K_{r1,r2,...,re,r,s,} n) has a realization G containing K_{r1,r2,...,re,r,s} as a subgraph, where s≥r≥re≥...≥r1≥0 and K_{r1,r2,...,re,r,s} is the r1 × r2 × ... × re × r × s complete (l + 2)-partite graph. In this paper, we determine σ(K_{r1,r2,...,re,2,s,} n) for s ≥ 3 and n ≥ 2s² + 8s + 3(r₁ + r₂ + .. + r_e) + 4.