Potentially $K_{1,1,t}$-Graphic Sequences

Abstract

Let $\omega (K_{1,1,t,}n)$ be the smallest even integer such that every $n$-term graphic sequence $\pi =(d_1,d_2,\dots ,d_n)$ with $\sigma (\pi )=d_1+d_2+\cdots +d_n\ge \sigma (K_{1,1,t,}n)$ has a realization $G$ containing $K_{1,1,t,}n$ as a subgraph, where $K_{1,1,t,}n$ is the $1\times 1\times t$ complete $3$-partite graph. Recently, Lai (Discrete Mathematics and Theoretical Computer Science, $7(2005),75-81)$ conjectured that for $n\ge 2t+4$,

$$\sigma (K_{1,1,t,}n)=\{\begin{array}{ll}(t+1)(n-1)+2& \text{if }n\text{ is odd or }t\text{ is odd,}\\ (t+1)(n-1)+1& \text{if }n\text{ and }t\text{ are even.}\end{array}$$

In this paper, we prove that the above equality holds for $n\ge t+4$.