Open Mathematics (Jun 2022)
Solutions to problems about potentially Ks,t-bigraphic pair
Abstract
Let S=(a1,…,am;b1,…,bn)S=\left({a}_{1},\ldots ,{a}_{m};\hspace{0.33em}{b}_{1},\ldots ,{b}_{n}), where a1,…,am{a}_{1},\ldots ,{a}_{m} and b1,…,bn{b}_{1},\ldots ,{b}_{n} are two nonincreasing sequences of nonnegative integers. The pair S=(a1,…,am;b1,…,bn)S=\left({a}_{1},\ldots ,{a}_{m};\hspace{0.33em}{b}_{1},\ldots ,{b}_{n}) is said to be a bigraphic pair if there is a simple bipartite graph G=(X∪Y,E)G=\left(X\cup Y,E) such that a1,…,am{a}_{1},\ldots ,{a}_{m} and b1,…,bn{b}_{1},\ldots ,{b}_{n} are the degrees of the vertices in XX and YY, respectively. In this case, GG is referred to as a realization of SS. Given a bigraphic pair SS, and a complete bipartite graph Ks,t{K}_{s,t}, we say that SS is a potentially Ks,t{K}_{s,t}-bigraphic pair if some realization of SS contains Ks,t{K}_{s,t} as a subgraph (with ss vertices in the part of size mm and tt in the part of size nn). Ferrara et al. (Potentially H-bigraphic sequences, Discuss. Math. Graph Theory 29 (2009), 583–596) defined σ(Ks,t,m,n)\sigma \left({K}_{s,t},m,n) to be the minimum integer kk such that every bigraphic pair S=(a1,…,am;b1,…,bn)S=\left({a}_{1},\ldots ,{a}_{m};{b}_{1},\ldots ,{b}_{n}) with σ(S)=a1+⋯+am≥k\sigma \left(S)={a}_{1}+\cdots +{a}_{m}\ge k is a potentially Ks,t{K}_{s,t}-bigraphic pair. This problem can be viewed as a “potential” degree sequence relaxation of the (forcible) Turán problem. Ferrara et al. determined σ(Ks,t,m,n)\sigma \left({K}_{s,t},m,n) for n≥m≥9s4t4n\ge m\ge 9{s}^{4}{t}^{4}. In this paper, we further determine σ(Ks,t,m,n)\sigma \left({K}_{s,t},m,n) for n≥m≥sn\ge m\ge s and n+m≥2t2+t+sn+m\ge 2{t}^{2}+t+s. As two corollaries, if n≥m≥t2+t+s2n\ge m\ge {t}^{2}+\frac{t+s}{2} or if n≥m≥sn\ge m\ge s and n≥2t2+tn\ge 2{t}^{2}+t, the values σ(Ks,t,m,n)\sigma \left({K}_{s,t},m,n) are determined completely. These results give a solution to a problem due to Ferrara et al. and a solution to a problem due to Yin and Wang.
Keywords
