Authors: S.-S. Li, J.-H. Yin Title: On factorable bigraphic pairs Source: Discussiones Mathematicae Graph Theory Received 15.09.2017, Revised 05.05.2018, Accepted 05.05.2018, doi: 10.7151/dmgt.2147 | |
Abstract: 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\le i\le m and d_{G}(y_{j})=b_{j} for 1\le j\le 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\le f_{i}\le k+1, 1\le i\le n (or k\le e_{i}\le k+1, 1\le i\le m), for some 0\le k\le m-1 (or 0\le k\le 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 | |
Links: |