DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

S.-S. Li, J.-H. Yin

Title:

On factorable bigraphic pairs

Source:

Discussiones Mathematicae Graph Theory

Received: 2017-09-15, Revised: 2018-05-05, Accepted: 2018-05-05, https://doi.org/10.7151/dmgt.2147

Abstract:

Let $S=(a_1,\ldots,a_m;$ $b_1,\ldots,b_n)$, where $a_1,\ldots,a_m$ and $b_1,\ldots,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,\ldots,x_m\}$ and $\{y_1,y_2,\ldots,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,\ldots,a_m;b_1,b_2,\ldots,b_n)$ and $(a_1-e_1,a_2-e_2,\ldots,a_m-e_m;$ $b_1-f_1,b_2-f_2,\ldots,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,\ldots,a_m;$ $b_1,b_2,\ldots,b_n)$ has a realization containing an $(e_1,e_2,\ldots,e_m;$ $f_1,f_2,\ldots,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\ge 2$. This implies a characterization of bigraphic pairs with a realization containing a Hamiltonian cycle.

Keywords:

degree sequence, bigraphic pair, Hamiltonian cycle

PDF
Close