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,\ldots,d_n)\) with \(\sigma(\pi) = d_1+d_2+\cdots+d_n \geq \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 \geq 2t+4\),

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

In this paper, we prove that the above equality holds for \(n \geq t+4\).