About an extremal problem of bigraphic pairs with a realization containing $K_{s,t}$

Yin, Jian-Hua  ; Wang, Bing

Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 437-444

Résumé

Let π=(f_1, … ,f_m;g_1, … ,g_n), where f_1, … ,f_m and g_1, … ,g_n are two non-increasing sequences of nonnegative integers. The pair π=(f_1,…,f_m; g_1,…,g_n) is said to be a bigraphic pair if there is a simple bipartite graph G=(X∪ Y,E) such that f_1,…,f_m and g_1,…,g_n are the degrees of the vertices in X and Y, respectively. In this case, G is referred to as a realization of π. We say that π is a potentially K_s,t-bigraphic pair if some realization of π contains K_s,t (with s vertices in the part of size m and t in the part of size n). Ferrara et al. [Potentially H-bigraphic sequences, Discuss. Math. Graph Theory 29 (2009) 583–596] defined σ(K_s,t,m,n) to be the minimum integer k such that every bigraphic pair π=(f_1,…,f_m;g_1,…,g_n) with σ(π)=f_1+⋯ +f_m≥ k is potentially K_s,t-bigraphic. They determined σ(K_s,t,m,n) for n≥ m≥ 9s^4t^4. In this paper, we first give a procedure and two sufficient conditions to determine if π is a potentially K_s,t-bigraphic pair. Then, we determine σ(K_s,t, m,n) for n≥ m≥ s and n≥ (s+1)t^2-(2s-1)t+s-1. This provides a solution to a problem due to Ferrara et al.

Détail

Keywords: bigraphic pair, realization, potentially $K_{s,t}$-bigraphic pair