1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

About an Extremal Problem of Bigraphic Pairs with a Realization Containing Ks,t1

Published Online: 16 Dec 2020
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 14 Jul 2020
Accepted: 23 Oct 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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 nm ≥ 9s4t4. 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

MSC 2010

[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. doi: 10.7151/dmgt.1466Open DOISearch in Google Scholar

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

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

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

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

Recommended articles from Trend MD

Plan your remote conference with Sciendo