The Characterization for a Graphic Sequence to have a Realization Containing K 1,1,s

摘要

A graphic sequence π = (d 1, d 2, . . . , d n ) is said to be potentially K 1,1,s -graphic if there is a realization of π containing K 1,1,s as a subgraph, where K 1,1,s is the 1 × 1 × s complete 3-partite graph. In this paper, a simple characterization of potentially K 1,1,s -graphic sequences for s ≥ 2 and n ≥ 3s + 1 is obtained. This characterization implies Lai’s conjecture on σ(K 1,1,s , n), which was confirmed by J.H. Yin, J.S. Li and W.Y. Li, and the values of σ(K 2,s , n) for s ≥ 4 and n ≥ 3s + 1, where K 2,s is the 2 × s complete bipartite graph.