×

On factorable bigraphic pairs. (English) Zbl 1439.05055

Summary: Let \(S = (a_1,\dots, a_m; b_1, \dots, b_n)\), where \(a_1, \dots, a_m\) and \(b_1, \dots, 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, \dots, x_m\}\) and \(\{y_1, y_2, \dots, y_n\}\) such that \(d_G (x_i) = a_i\) for \(1 \leq i \leq m\) and \(d_G (y_j) = b_j\) for \(1 \leq j \leq n\). In this case, we say that \(G\) is a realization of \(S\). Analogous to Kundu’s \(k\)-factor theorem [S. Kundu, Discrete Math. 6, 367–376 (1973; Zbl 0278.05115)], we show that if \((a_1, a_2, \dots, a_m; b_1, b_2,\dots, b_n)\) and \((a_1 - e_1, a_2 - e_2, \dots, a_m - e_m; b_1 - f_1, b_2 - f_2, \dots, b_n - f_n)\) are two bigraphic pairs satisfying \(k \leq f_i \leq k + 1\), \(1 \leq i \leq n\) (or \(k \leq e_i \leq k + 1\), \(1 \leq i \leq m)\), for some \(0 \leq k \leq m - 1\) (or \(0 \leq k \leq n - 1)\), then \((a_1, a_2, \dots, a_m; b_1, b_2, \dots, b_n)\) has a realization containing an \((e_1, e_2, \dots, e_m; f_1, f_2, \dots, 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 \geq 2\). This implies a characterization of bigraphic pairs with a realization containing a Hamiltonian cycle.

MSC:

05C07 Vertex degrees
05C45 Eulerian and Hamiltonian graphs

Citations:

Zbl 0278.05115
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (American Elsevier, New York, 1976). · Zbl 1226.05083
[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 · Zbl 0651.05054
[3] D. Gale, A theorem on flows in networks, Pacific J. Math. 7 (1957) 1073-1082. doi:10.2140/pjm.1957.7.1073 · Zbl 0087.16303
[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 · Zbl 0263.05122
[5] S. Kundu, The k-factor conjecture is true, Discrete Math. 6 (1973) 367-376. doi:10.1016/0012-365X(73)90068-X · Zbl 0278.05115
[6] S. Kundu, Generalizations of the k-factor theorem, Discrete Math. 9 (1974) 173-179. doi:10.1016/0012-365X(74)90147-2 · Zbl 0285.05120
[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 · Zbl 0224.05126
[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 · Zbl 0079.01102
[9] J.H. Yin, A characterization for a graphic sequence to be potentially C_r-graphic, Sci. China Math. 53 (2010) 2893-2905. doi:10.1007/s11425-010-3124-6 · Zbl 1226.05092
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.