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

Abstract

top
Let be the complete bipartite graph with partite sets and . A split bipartite-graph on vertices, denoted by , is the graph obtained from by adding new vertices , such that each of is adjacent to each of and each of is adjacent to each of . Let and be nonincreasing lists of nonnegative integers, having lengths and , respectively. The pair is potentially -bigraphic if there is a simple bipartite graph containing (with vertices in the part of size and vertices in the part of size ) such that the lists of vertex degrees in the two partite sets are and . In this paper, we give a characterization for to be potentially -bigraphic. A simplification of this characterization is also presented.

How to cite

top

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 -

References

top
  1. Erdős, P., Gallai, T., Graphs with prescribed degrees of vertices, Mat. Lapok 11 Hungarian (1961), 264-274. (1961) Zbl0103.39701
  2. 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
  3. Gale, D., 10.2140/pjm.1957.7.1073, Pac. J. Math. 7 (1957), 1073-1082. (1957) Zbl0087.16303MR0091855DOI10.2140/pjm.1957.7.1073
  4. 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
  5. 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
  6. Nash-Williams, C. St. J. A., Valency sequences which force graphs to have hamiltonian circuits, Interim Report University of Waterloo, Waterloo (1970). (1970) 
  7. Rao, A. R., An Erdős-Gallai type result on the clique number of a realization of a degree sequence, Unpublished. 
  8. Ryser, H. J., 10.4153/CJM-1957-044-3, Canad. J. Math. 9 (1957), 371-377. (1957) Zbl0079.01102MR0087622DOI10.4153/CJM-1957-044-3
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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 ?

top

You must be logged in to post comments.