Article in volume
Authors:
Title:
About an extremal problem of bigraphic pairs with a realization containing $K_{s,t}$
PDFSource:
Discussiones Mathematicae Graph Theory 43(2) (2023) 437-444
Received: 2020-07-14 , Revised: 2020-10-23 , Accepted: 2020-10-23 , Available online: 2020-11-20 , https://doi.org/10.7151/dmgt.2375
Abstract:
Let $\pi=(f_1,\dots,f_m;g_1,\dots,g_n)$, where $f_1,\dots,f_m$ and
$g_1,\dots,g_n$ are two non-increasing sequences of nonnegative integers.
The pair $\pi=(f_1,\dots,f_m;$ $g_1,\dots,g_n)$ is said to be a bigraphic
pair if there is a simple bipartite graph $G=(X\cup Y,E)$ such that
$f_1,\dots,f_m$ and $g_1,\dots,g_n$ are the degrees of the vertices in $X$
and $Y$, respectively. In this case, $G$ is referred to as a realization
of $\pi$. We say that $\pi$ is a potentially $K_{s,t}$-bigraphic pair if
some realization of $\pi$ 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 $\sigma(K_{s,t},m,n)$ to be the minimum integer $k$
such that every bigraphic pair $\pi=(f_1,\dots,f_m;g_1,\dots,g_n)$ with
$\sigma(\pi)=f_1+\cdots +f_m\ge k$ is potentially $K_{s,t}$-bigraphic.
They determined $\sigma(K_{s,t},m,n)$ for $n\ge m\ge 9s^4t^4$. In this paper,
we first give a procedure and two sufficient conditions to determine if $\pi$
is a potentially $K_{s,t}$-bigraphic pair. Then, we determine $\sigma(K_{s,t},
m,n)$ for $n\ge m\ge s$ and $n\ge (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
References:
- 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 - D. Gale, A theorem on flows in networks, Pacific J. Math. 7 (1957) 1073–1082.
https://doi.org/10.2140/pjm.1957.7.1073 - 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 - 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 - J.H. Yin, A note on potentially $K_{s,t}$-bigraphic pairs, Util. Math. 100 (2016) 407–410.
Close