On Factorable Bigraphic Pairs

Yin, Jian-Hua ; Li, Sha-Sha

Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 787-793

Résumé

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.

Détail

Keywords: degree sequence, bigraphic pair, Hamiltonian cycle