An extremal problem on potentially \(K_{r,s}\)-graphic sequences (Q1861273): Difference between revisions

The authors study a variant of the Turán-type extremal problem (defined by Erdős et al.) as follows: Determine the smallest even integer \(\sigma(K_{r,s},n)\) such that every \(n\)-term graphic sequence \(\pi= (d_1,d_2,\dots, d_n)\) with term sum \(\sigma(\pi)= d_1+ d_2+\cdots+ d_n\geq \sigma(K_{r,s},n)\) is potentially \(K_{r,s}\)-graphic, where \(K_{r,s}\) is an \(r\times s\) complete bipartite graph. They give several sufficient conditions for a graphic sequence to be potentially \(K_{r,s}\)-graphic and prove the exact value of \(\sigma(K_{r,s},n)\) for \(r= 3, 4\). The explanation of relations between previous extremal results and these results is very clear.