Geodesic
About an extremal problem of bigraphic pairs with a realization containing $K_{s,t}$
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 437-444

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: bigraphic pair, realization, potentially $K_{s,t}$-bigraphic pair 
Yin, Jian-Hua; Wang, Bing. About an extremal problem of bigraphic pairs with a realization containing $K_{s,t}$. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 437-444. http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a7/
@article{DMGT_2023_43_2_a7,
     author = {Yin, Jian-Hua and Wang, Bing},
     title = {About an extremal problem of bigraphic pairs with a realization containing $K_{s,t}$},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {437--444},
     year = {2023},
     volume = {43},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a7/}
}
TY  - JOUR
AU  - Yin, Jian-Hua
AU  - Wang, Bing
TI  - About an extremal problem of bigraphic pairs with a realization containing $K_{s,t}$
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 437
EP  - 444
VL  - 43
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a7/
LA  - en
ID  - DMGT_2023_43_2_a7
ER  - 
%0 Journal Article
%A Yin, Jian-Hua
%A Wang, Bing
%T About an extremal problem of bigraphic pairs with a realization containing $K_{s,t}$
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 437-444
%V 43
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a7/
%G en
%F DMGT_2023_43_2_a7

[1] M.J. Ferrara, M.S. Jacobson, J.R. Schmitt and M. Siggers, Potentially H-bigraphic sequences, Discuss. Math. Graph Theory 29 (2009) 583–596. https://doi.org/10.7151/dmgt.1466

[2] D. Gale, A theorem on flows in networks, Pacific J. Math. 7 (1957) 1073–1082. https://doi.org/10.2140/pjm.1957.7.1073

[3] H.J. Ryser, Combinatorial properties of matrices of zeros and ones, Canad. J. Math. 9 (1957) 371–377. https://doi.org/10.4153/CJM-1957-044-3

[4] J.H. Yin, An extremal problem on bigraphic pairs with an A-connected realization, Discrete Math. 339 (2016) 2018–2026. https://doi.org/10.1016/j.disc.2016.02.014

[5] J.H. Yin, A note on potentially Ks,t-bigraphic pairs, Util. Math. 100 (2016) 407–410.