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=(a1,...,am; b1,...,bn), where a1,...,am and b1,...,bn 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 {x1,x2,...,xm} and {y1,y2,...,yn} such that dG(xi)=ai for 1\le i\le m and dG(yj)=bj 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 (a1,a2,...,am;b1,b2,...,bn) and (a1-e1,a2-e2,...,am-em; b1-f1,b2-f2,...,bn-fn) are two bigraphic pairs satisfying k\le fi\le k+1, 1\le i\le n (or k\le ei\le k+1, 1\le i\le m), for some 0\le k\le m-1 (or 0\le k\le n-1), then (a1,a2,...,am; b1,b2,...,bn) has a realization containing an (e1,e2,...,em; f1,f2,...,fn)-factor. For m=n, we also give a necessary and sufficient condition for an (kn;kn)-factorable bigraphic pair to be connected (kn;kn)-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:
PDF