| Title:
|
Bigraphic pairs with a realization containing a split bipartite-graph (English) |
| Author:
|
Yin, Jian-Hua |
| Author:
|
Li, Jia-Yun |
| Author:
|
Du, Jin-Zhi |
| Author:
|
Li, Hai-Yan |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
69 |
| Issue:
|
3 |
| Year:
|
2019 |
| Pages:
|
609-619 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
degree sequence |
| Keyword:
|
bigraphic pair |
| Keyword:
|
potentially ${\rm SB}_{s+s',t+t'}$-bigraphic pair |
| MSC:
|
05C07 |
| idZBL:
|
Zbl 07088807 |
| idMR:
|
MR3989269 |
| DOI:
|
10.21136/CMJ.2019.0076-17 |
| . |
| Date available:
|
2019-07-24T11:14:40Z |
| Last updated:
|
2021-10-04 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/147780 |
| . |
| Reference:
|
[1] Erdős, P., Gallai, T.: Graphs with prescribed degrees of vertices.Mat. Lapok 11 Hungarian (1961), 264-274. Zbl 0103.39701 |
| Reference:
|
[2] Ferrara, M., Jacobson, M., Schmitt, J., Siggers, M.: Potentially {$H$}-bigraphic sequences.Discuss. Math., Graph Theory 29 (2009), 583-596. Zbl 1194.05022, MR 2642803, 10.7151/dmgt.1466 |
| Reference:
|
[3] Gale, D.: A theorem on flows in networks.Pac. J. Math. 7 (1957), 1073-1082. Zbl 0087.16303, MR 0091855, 10.2140/pjm.1957.7.1073 |
| Reference:
|
[4] Garg, A., Goel, A., Tripathi, A.: Constructive extensions of two results on graphic sequences.Discrete Appl. Math. 159 (2011), 2170-2174. Zbl 1239.05035, MR 2832340, 10.1016/j.dam.2011.06.017 |
| Reference:
|
[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. Zbl 024.00517, MR 1985084 |
| Reference:
|
[6] Nash-Williams, C. St. J. A.: Valency sequences which force graphs to have hamiltonian circuits.Interim Report University of Waterloo, Waterloo (1970). |
| Reference:
|
[7] Rao, A. R.: An Erdős-Gallai type result on the clique number of a realization of a degree sequence.Unpublished. |
| Reference:
|
[8] Ryser, H. J.: Combinatorial properties of matrices of zeros and ones.Canad. J. Math. 9 (1957), 371-377. Zbl 0079.01102, MR 0087622, 10.4153/CJM-1957-044-3 |
| Reference:
|
[9] Tripathi, A., Venugopalan, S., West, D. B.: A short constructive proof of the Erdős-Gallai characterization of graphic lists.Discrete Math. 310 (2010), 843-844. Zbl 1209.05058, MR 2574834, 10.1016/j.disc.2009.09.023 |
| Reference:
|
[10] Yin, J.-H.: A Rao-type characterization for a sequence to have a realization containing a split graph.Discrete Math. 311 (2011), 2485-2489. Zbl 1238.05063, MR 2832147, 10.1016/j.disc.2011.07.024 |
| Reference:
|
[11] Yin, J.-H.: A short constructive proof of A.R. Rao's characterization of potentially {$K_{r+1}$}-graphic sequences.Discrete Appl. Math. 160 (2012), 352-354. Zbl 1241.05143, MR 2862342, 10.1016/j.dam.2011.10.015 |
| Reference:
|
[12] Yin, J.-H.: A note on potentially {$K_{s,t}$}-bigraphic pairs.Util. Math. 100 (2016), 407-410. Zbl 1353.05038, MR 3526677, 10.1016/j.disc.2011.07.024 |
| Reference:
|
[13] Yin, J.-H., Huang, X.-F.: A Gale-Ryser type characterization of potentially {$K_{s,t}$}-bigraphic pairs.Discrete Math. 312 (2012), 1241-1243. Zbl 1238.05064, MR 2876373, 10.1016/j.disc.2011.12.016 |
| . |
