Bigraphic pairs with a realization containing a split bipartite-graph

Yin, Jian-Hua ; Li, Jia-Yun ; Du, Jin-Zhi ; Li, Hai-Yan

Czechoslovak Mathematical Journal, Tome 69 (2019) no. 3, pp. 609-619

Résumé

Let $K_{s,t}$ be the complete bipartite graph with partite sets $\{x_1,\ldots ,x_s\}$ and $\{y_1,\ldots ,y_t\}$. A split bipartite-graph on $(s+s')+(t+t')$ vertices, denoted by ${\rm SB}_{s+s',t+t'}$, is the graph obtained from $K_{s,t}$ by adding $s'+t'$ new vertices $x_{s+1},\ldots ,x_{s+s'}$, $y_{t+1},\ldots ,y_{t+t'}$ such that each of $x_{s+1},\ldots ,x_{s+s'}$ is adjacent to each of $y_1,\ldots ,y_t$ and each of $y_{t+1},\ldots ,y_{t+t'}$ is adjacent to each of $x_1,\ldots ,x_s$. Let $A$ and $B$ be nonincreasing lists of nonnegative integers, having lengths $m$ and $n$, respectively. The pair $(A;B)$ is potentially ${\rm SB}_{s+s',t+t'}$-bigraphic if there is a simple bipartite graph containing ${\rm SB}_{s+s',t+t'}$ (with $s+s'$ vertices $x_1,\ldots ,x_{s+s'}$ in the part of size $m$ and $t+t'$ vertices $y_1,\ldots ,y_{t+t'}$ in the part of size $n$) such that the lists of vertex degrees in the two partite sets are $A$ and $B$. In this paper, we give a characterization for $(A;B)$ to be potentially ${\rm SB}_{s+s',t+t'}$-bigraphic. A simplification of this characterization is also presented.

Détail

DOI : 10.21136/CMJ.2019.0076-17

Classification : 05C07
Keywords: degree sequence; bigraphic pair; potentially ${\rm SB}_{s+s', t+t'}$-bigraphic pair