Geodesic
A Constructive Extension of the Characterization on Potentially Ks,t-Bigraphic Pairs
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 1, pp. 251-259.

Voir la notice de l'article provenant de la source Library of Science

Let Ks,t be the complete bipartite graph with partite sets of size s and t. Let L1 = ([a1, b1], . . ., [am, bm]) and L2 = ([c1, d1], . . ., [cn, dn]) be two sequences of intervals consisting of nonnegative integers with a1 ≥ a2 ≥ . . . ≥ am and c1 ≥ c2 ≥ . . . ≥ cn. We say that L = (L1; L2) is potentially Ks,t (resp. As,t)-bigraphic if there is a simple bipartite graph G with partite sets X = x1, . . ., xm and Y = y1, . . ., yn such that ai ≤ dG(xi) ≤ bi for 1 ≤ i ≤ m, ci ≤ dG(yi) ≤ di for 1 ≤ i ≤ n and G contains Ks,t as a subgraph (resp. the induced subgraph of x1, . . ., xs, y1, . . ., yt in G is a Ks,t). In this paper, we give a characterization of L that is potentially As,t-bigraphic. As a corollary, we also obtain a characterization of L that is potentially Ks,t-bigraphic if b1 ≥ b2 ≥ . . . ≥ bm and d1 ≥ d2 ≥ . . . ≥ dn. This is a constructive extension of the characterization on potentially Ks,t-bigraphic pairs due to Yin and Huang (Discrete Math. 312 (2012) 1241–1243).
Keywords: degree sequence, bigraphic pair, potentially K s,t -bigraphic pair 
@article{DMGT_2017_37_1_a17,
     author = {Guo, Ji-Yun and Yin, Jian-Hua},
     title = {A {Constructive} {Extension} of the {Characterization} on {Potentially} {K\protect\textsubscript{s,t}-Bigraphic} {Pairs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {251--259},
     publisher = {mathdoc},
     volume = {37},
     number = {1},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a17/}
}
TY  - JOUR
AU  - Guo, Ji-Yun
AU  - Yin, Jian-Hua
TI  - A Constructive Extension of the Characterization on Potentially Ks,t-Bigraphic Pairs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 251
EP  - 259
VL  - 37
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a17/
LA  - en
ID  - DMGT_2017_37_1_a17
ER  - 
%0 Journal Article
%A Guo, Ji-Yun
%A Yin, Jian-Hua
%T A Constructive Extension of the Characterization on Potentially Ks,t-Bigraphic Pairs
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 251-259
%V 37
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a17/
%G en
%F DMGT_2017_37_1_a17
Guo, Ji-Yun; Yin, Jian-Hua. A Constructive Extension of the Characterization on Potentially Ks,t-Bigraphic Pairs. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 1, pp. 251-259. http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a17/

[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] A. Garg, A. Goel and A. Tripathi, Constructive extensions of two results on graphic sequences, Discrete Appl. Math. 159 (2011) 2170–2174. doi:10.1016/j.dam.2011.06.017

[4] 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

[5] A. Tripathi, S. Venugopalan and D.B. West, A short constructive proof of the Erdös-Gallai characterization of graphic lists, Discrete Math. 310 (2010) 843–844. doi:10.1016/j.disc.2009.09.023

[6] J.H. Yin and X.F. Huang, A Gale-Ryser type characterization of potentially Ks,t-bigraphic pairs, Discrete Math. 312 (2012) 1241–1243. doi:10.1016/j.disc.2011.12.016