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.