# Bigraphic pairs with a realization containing a split bipartite-graph

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

Czechoslovak Mathematical Journal (2019)

- Volume: 69, Issue: 3, page 609-619
- ISSN: 0011-4642

## Access Full Article

top## Abstract

top## How to cite

topYin, 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 -

## References

top- Erdős, P., Gallai, T., Graphs with prescribed degrees of vertices, Mat. Lapok 11 Hungarian (1961), 264-274. (1961) Zbl0103.39701
- Ferrara, M., Jacobson, M., Schmitt, J., Siggers, M., 10.7151/dmgt.1466, Discuss. Math., Graph Theory 29 (2009), 583-596. (2009) Zbl1194.05022MR2642803DOI10.7151/dmgt.1466
- Gale, D., 10.2140/pjm.1957.7.1073, Pac. J. Math. 7 (1957), 1073-1082. (1957) Zbl0087.16303MR0091855DOI10.2140/pjm.1957.7.1073
- Garg, A., Goel, A., Tripathi, A., 10.1016/j.dam.2011.06.017, Discrete Appl. Math. 159 (2011), 2170-2174. (2011) Zbl1239.05035MR2832340DOI10.1016/j.dam.2011.06.017
- Kézdy, A., Lehel, J., Degree sequences of graphs with prescribed clique size, Combinatorics, Graph Theory, and Algorithms, Vol. I, II New Issues Press, Kalamazoo Y. Alavi et al. (1999), 535-544. (1999) MR1985084
- Nash-Williams, C. St. J. A., Valency sequences which force graphs to have hamiltonian circuits, Interim Report University of Waterloo, Waterloo (1970). (1970)
- Rao, A. R., An Erdős-Gallai type result on the clique number of a realization of a degree sequence, Unpublished.
- Ryser, H. J., 10.4153/CJM-1957-044-3, Canad. J. Math. 9 (1957), 371-377. (1957) Zbl0079.01102MR0087622DOI10.4153/CJM-1957-044-3
- Tripathi, A., Venugopalan, S., West, D. B., 10.1016/j.disc.2009.09.023, Discrete Math. 310 (2010), 843-844. (2010) Zbl1209.05058MR2574834DOI10.1016/j.disc.2009.09.023
- Yin, J.-H., 10.1016/j.disc.2011.07.024, Discrete Math. 311 (2011), 2485-2489. (2011) Zbl1238.05063MR2832147DOI10.1016/j.disc.2011.07.024
- Yin, J.-H., 10.1016/j.dam.2011.10.015, Discrete Appl. Math. 160 (2012), 352-354. (2012) Zbl1241.05143MR2862342DOI10.1016/j.dam.2011.10.015
- Yin, J.-H., 10.1016/j.disc.2011.07.024, Util. Math. 100 (2016), 407-410. (2016) Zbl1353.05038MR3526677DOI10.1016/j.disc.2011.07.024
- Yin, J.-H., Huang, X.-F., 10.1016/j.disc.2011.12.016, Discrete Math. 312 (2012), 1241-1243. (2012) Zbl1238.05064MR2876373DOI10.1016/j.disc.2011.12.016

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.