Bigraphic pairs with a realization containing a split bipartite-graph

Yin, Jian Hua, et al. "Bigraphic pairs with a realization containing a split bipartite-graph." Czechoslovak Mathematical Journal 69.3 (2019): 609-619. <http://eudml.org/doc/294606>.

@article{Yin2019,
abstract = {Let $K_\{s,t\}$ be the complete bipartite graph with partite sets $\lbrace x_1,\ldots ,x_s\rbrace $ and $\lbrace y_1,\ldots ,y_t\rbrace $. A split bipartite-graph on $(s+s^\{\prime \})+(t+t^\{\prime \})$ vertices, denoted by $\{\rm SB\}_\{s+s^\{\prime \},t+t^\{\prime \}\}$, is the graph obtained from $K_\{s,t\}$ by adding $s^\{\prime \}+t^\{\prime \}$ new vertices $x_\{s+1\},\ldots ,x_\{s+s^\{\prime \}\}$, $y_\{t+1\},\ldots ,y_\{t+t^\{\prime \}\}$ such that each of $x_\{s+1\},\ldots ,x_\{s+s^\{\prime \}\}$ is adjacent to each of $y_1,\ldots ,y_t$ and each of $y_\{t+1\},\ldots ,y_\{t+t^\{\prime \}\}$ 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^\{\prime \},t+t^\{\prime \}\}$-bigraphic if there is a simple bipartite graph containing $\{\rm SB\}_\{s+s^\{\prime \},t+t^\{\prime \}\}$ (with $s+s^\{\prime \}$ vertices $x_1,\ldots ,x_\{s+s^\{\prime \}\}$ in the part of size $m$ and $t+t^\{\prime \}$ vertices $y_1,\ldots ,y_\{t+t^\{\prime \}\}$ 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^\{\prime \},t+t^\{\prime \}\}$-bigraphic. A simplification of this characterization is also presented.},
author = {Yin, Jian Hua, Li, Jia-Yun, Du, Jin-Zhi, Li, Hai-Yan},
journal = {Czechoslovak Mathematical Journal},
keywords = {degree sequence; bigraphic pair; potentially $\{\rm SB\}_\{s+s^\{\prime \},t+t^\{\prime \}\}$-bigraphic pair},
language = {eng},
number = {3},
pages = {609-619},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Bigraphic pairs with a realization containing a split bipartite-graph},
url = {http://eudml.org/doc/294606},
volume = {69},
year = {2019},
}

TY - JOUR
AU - Yin, Jian Hua
AU - Li, Jia-Yun
AU - Du, Jin-Zhi
AU - Li, Hai-Yan
TI - Bigraphic pairs with a realization containing a split bipartite-graph
JO - Czechoslovak Mathematical Journal
PY - 2019
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 69
IS - 3
SP - 609
EP - 619
AB - Let $K_{s,t}$ be the complete bipartite graph with partite sets $\lbrace x_1,\ldots ,x_s\rbrace $ and $\lbrace y_1,\ldots ,y_t\rbrace $. A split bipartite-graph on $(s+s^{\prime })+(t+t^{\prime })$ vertices, denoted by ${\rm SB}_{s+s^{\prime },t+t^{\prime }}$, is the graph obtained from $K_{s,t}$ by adding $s^{\prime }+t^{\prime }$ new vertices $x_{s+1},\ldots ,x_{s+s^{\prime }}$, $y_{t+1},\ldots ,y_{t+t^{\prime }}$ such that each of $x_{s+1},\ldots ,x_{s+s^{\prime }}$ is adjacent to each of $y_1,\ldots ,y_t$ and each of $y_{t+1},\ldots ,y_{t+t^{\prime }}$ 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^{\prime },t+t^{\prime }}$-bigraphic if there is a simple bipartite graph containing ${\rm SB}_{s+s^{\prime },t+t^{\prime }}$ (with $s+s^{\prime }$ vertices $x_1,\ldots ,x_{s+s^{\prime }}$ in the part of size $m$ and $t+t^{\prime }$ vertices $y_1,\ldots ,y_{t+t^{\prime }}$ 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^{\prime },t+t^{\prime }}$-bigraphic. A simplification of this characterization is also presented.
LA - eng
KW - degree sequence; bigraphic pair; potentially ${\rm SB}_{s+s^{\prime },t+t^{\prime }}$-bigraphic pair
UR - http://eudml.org/doc/294606
ER -