Journal Details
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Open Access

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

###### Accepted: 23 Oct 2020
Journal Details
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English

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.

#### 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.1466

[2] D. Gale, A theorem on flows in networks, Pacific J. Math. 7 (1957) 1073–1082. doi: 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. doi: 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. doi: 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.Search in Google Scholar

• #### A Note About Monochromatic Components in Graphs of Large Minimum Degree

Recommended articles from Trend MD