An extremal problem on potentially \(K_{r,s}\)-graphic sequences (Q1861273)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An extremal problem on potentially \(K_{r,s}\)-graphic sequences |
scientific article |
Statements
An extremal problem on potentially \(K_{r,s}\)-graphic sequences (English)
0 references
16 March 2003
0 references
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.
0 references
degree sequence
0 references
potentially \(K_{r,s}\)-graphic sequence
0 references