DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

J.-H. Yin

Jianhua Yin

School of Science, Hainan University\
Haikou 570228, P.R. China

email: yinjh@hainanu.edu.cn

B. Wang

Bing Wang

School of Science, Hainan University
Haikou 570228, P.R. China

email: 504791551@qq.com

Title:

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

PDF

Source:

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:

  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 $K_{s,t}$-bigraphic pairs, Util. Math. 100 (2016) 407–410.

Close