Geodesic
On Factorable Bigraphic Pairs
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 787-793.

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

Let S = (a_1,. . ., a_m; b_1, . . ., b_n), where a_1, . . ., a_m and b_1, . . ., b_n are two sequences of nonnegative integers. We say that S is a bigraphic pair if there exists a simple bipartite graph G with partite sets x_1, x_2, . . ., x_m and y_1, y_2, . . ., y_n such that d_G(x_i) = a_i for 1 ≤ i ≤ m and d_G(y_j) = b_j for 1 ≤ j ≤ n. In this case, we say that G is a realization of S. Analogous to Kundu’s k-factor theorem, we show that if (a_1, a_2, . . ., a_m; b_1, b_2, . . ., b_n) and (a_1 − e_1, a_2 − e_2, . . ., a_m − e_m; b_1 − f_1, b_2 − f_2, . . ., b_n − f_n) are two bigraphic pairs satisfying k ≤ f_i ≤ k + 1, 1 ≤ i ≤ n (ork ≤ e_i ≤ k + 1, 1 ≤ i ≤ m), for some 0 ≤ k ≤ m − 1 (or 0 ≤ k ≤ n − 1), then (a_1, a_2, . . ., a_m; b_1, b_2, . . ., b_n) has a realization containing an (e_1, e_2, . . ., e_m; f_1, f_2, . . ., f_n)-factor. For m = n, we also give a necessary and sufficient condition for an (k^n; k^n)-factorable bigraphic pair to be connected (k^n; k^n)-factorable when k ≥ 2. This implies a characterization of bigraphic pairs with a realization containing a Hamiltonian cycle.
Keywords: degree sequence, bigraphic pair, Hamiltonian cycle 
@article{DMGT_2020_40_3_a5,
     author = {Yin, Jian-Hua and Li, Sha-Sha},
     title = {On {Factorable} {Bigraphic} {Pairs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {787--793},
     publisher = {mathdoc},
     volume = {40},
     number = {3},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a5/}
}
TY  - JOUR
AU  - Yin, Jian-Hua
AU  - Li, Sha-Sha
TI  - On Factorable Bigraphic Pairs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 787
EP  - 793
VL  - 40
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a5/
LA  - en
ID  - DMGT_2020_40_3_a5
ER  - 
%0 Journal Article
%A Yin, Jian-Hua
%A Li, Sha-Sha
%T On Factorable Bigraphic Pairs
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 787-793
%V 40
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a5/
%G en
%F DMGT_2020_40_3_a5
Yin, Jian-Hua; Li, Sha-Sha. On Factorable Bigraphic Pairs. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 787-793. http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a5/

[1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (American Elsevier, New York, 1976).

[2] Y. Chen, A short proof of Kundu’s k-factor theorem, Discrete Math. 71 (1988) 177–179. doi:10.1016/0012-365X(88)90070-2

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

[4] D.J. Kleitman and D.L. Wang, Algorithm for constructing graphs and digraphs with given valences and factors, Discrete Math. 6 (1973) 79–88. doi:10.1016/0012-365X(73)90037-X

[5] S. Kundu, The k-factor conjecture is true, Discrete Math. 6 (1973) 367–376. doi:10.1016/0012-365X(73)90068-X

[6] S. Kundu, Generalizations of the k-factor theorem, Discrete Math. 9 (1974) 173–179. doi:10.1016/0012-365X(74)90147-2

[7] A.R. Rao and S.B. Rao, On factorable degree sequences, J. Combin. Theory Ser. B 13 (1972) 185–191. doi:10.1016/0095-8956(72)90055-X

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

[9] J.H. Yin, A characterization for a graphic sequence to be potentially Cr -graphic, Sci. China Math. 53 (2010) 2893–2905. doi:10.1007/s11425-010-3124-6