Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
degree sequence; bigraphic pair; potentially ${\rm SB}_{s+s',t+t'}$-bigraphic pair
degree sequence; bigraphic pair; potentially ${\rm SB}_{s+s',t+t'}$-bigraphic pair
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.
References:
[1] Erdős, P., Gallai, T.: Graphs with prescribed degrees of vertices. Mat. Lapok 11 Hungarian (1961), 264-274. Zbl 0103.39701
[2] Ferrara, M., Jacobson, M., Schmitt, J., Siggers, M.: Potentially {$H$}-bigraphic sequences. Discuss. Math., Graph Theory 29 (2009), 583-596. DOI 10.7151/dmgt.1466 | MR 2642803 | Zbl 1194.05022
[3] Gale, D.: A theorem on flows in networks. Pac. J. Math. 7 (1957), 1073-1082. DOI 10.2140/pjm.1957.7.1073 | MR 0091855 | Zbl 0087.16303
[4] Garg, A., Goel, A., Tripathi, A.: Constructive extensions of two results on graphic sequences. Discrete Appl. Math. 159 (2011), 2170-2174. DOI 10.1016/j.dam.2011.06.017 | MR 2832340 | Zbl 1239.05035
[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. MR 1985084 | Zbl 024.00517
[6] Nash-Williams, C. St. J. A.: Valency sequences which force graphs to have hamiltonian circuits. Interim Report University of Waterloo, Waterloo (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.: Combinatorial properties of matrices of zeros and ones. Canad. J. Math. 9 (1957), 371-377. DOI 10.4153/CJM-1957-044-3 | MR 0087622 | Zbl 0079.01102
[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. DOI 10.1016/j.disc.2009.09.023 | MR 2574834 | Zbl 1209.05058
[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. DOI 10.1016/j.disc.2011.07.024 | MR 2832147 | Zbl 1238.05063
[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. DOI 10.1016/j.dam.2011.10.015 | MR 2862342 | Zbl 1241.05143
[12] Yin, J.-H.: A note on potentially {$K_{s,t}$}-bigraphic pairs. Util. Math. 100 (2016), 407-410. DOI 10.1016/j.disc.2011.07.024 | MR 3526677 | Zbl 1353.05038
[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. DOI 10.1016/j.disc.2011.12.016 | MR 2876373 | Zbl 1238.05064
Search
Partner of
