ArticleOriginal scientific textAbout an extremal problem of bigraphic pairs with a realization containing
Title
About an extremal problem of bigraphic pairs with a realization containing
Authors * 1, 1
*Corresponding author
Affiliations
- School of Science, Hainan University, Haikou 570228, P.R. China
Abstract
Let , where and are two non-increasing sequences of nonnegative integers. The pair is said to be a bigraphic pair if there is a simple bipartite graph such that and are the degrees of the vertices in and , respectively. In this case, is referred to as a realization of . We say that is a potentially -bigraphic pair if some realization of contains (with vertices in the part of size and in the part of size ). Ferrara et al. [Potentially -bigraphic sequences, Discuss. Math. Graph Theory 29 (2009) 583–596] defined to be the minimum integer such that every bigraphic pair with is potentially -bigraphic. They determined for . In this paper, we first give a procedure and two sufficient conditions to determine if is a potentially -bigraphic pair. Then, we determine for and . This provides a solution to a problem due to Ferrara et al.
Keywords
bigraphic pair, realization, potentially -bigraphic pair
Bibliography
- 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 Ks,t-bigraphic pairs, Util. Math. 100 (2016) 407–410.