Turan number for \(pS_r\)

Jian-Hua Yin, Yang Rao1
1Department of Math., College of Information Science and Technology, Hainan University, Haikou 570228, P.R. China

Abstract

The Turán number \(ex(m, G)\) of the graph \(G\) is the maximum number of edges of an \(m\)-vertex simple graph having no \(G\) as a subgraph. A \emph{star} \(S_r\) is the complete bipartite graph \(K_{1,r}\) (or a tree with one internal vertex and \(r\) leaves) and \(pS_r\) denotes the disjoint union of \(p\) copies of \(S_r\). A result of Lidický et al. (Electron. J. Combin. \(20(2)(2013) P62\)) implies that \(ex(m,pS_r) = \left\lfloor\frac{(m-p+1)(r-1)}{2}\right\rfloor + (p-1)m – \binom{p}{2}\) for \(m\) sufficiently large. In this paper, we give another proof and show that \(ex(m,pS_r) = \left\lfloor \frac{(m-p+1)(r-1)}{2}\right\rfloor + (p-1)m – \binom{p}{2}\) for all \(r \geq 1\), \(p \geq 1\), and \(m \geq \frac{1}{2}r^2p(p – 1) + p – 2 + \max\{rp, r^2 + 2r\}\).

Keywords: Turdn number, Disjoint copies, pS,.