ArticleOriginal scientific text

Title

About an extremal problem of bigraphic pairs with a realization containing Ks,t

Authors * 1, 1

*Corresponding author

Affiliations

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

Abstract

Let π=(f1,...,fm;g1,...,gn), where f1,...,fm and g1,...,gn are two non-increasing sequences of nonnegative integers. The pair π=(f1,...,fm; g1,...,gn) is said to be a bigraphic pair if there is a simple bipartite graph G=(XY,E) such that f1,...,fm and g1,...,gn 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 Ks,t-bigraphic pair if some realization of π contains Ks,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 σ(Ks,t,m,n) to be the minimum integer k such that every bigraphic pair π=(f1,...,fm;g1,...,gn) with σ(π)=f1++fmk is potentially Ks,t-bigraphic. They determined σ(Ks,t,m,n) for nm9s4t4. In this paper, we first give a procedure and two sufficient conditions to determine if π is a potentially Ks,t-bigraphic pair. Then, we determine σ(Ks,t,m,n) for nms and n(s+1)t2-(2s-1)t+s-1. This provides a solution to a problem due to Ferrara et al.

Keywords

bigraphic pair, realization, potentially Ks,t-bigraphic pair

Bibliography

  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.
Pages:
437-444
Main language of publication
English
Published
2023
Published online
2023-01-09
Exact and natural sciences