Geodesic
Bigraphic pairs with a realization containing a split bipartite-graph
Czechoslovak Mathematical Journal, Tome 69 (2019) no. 3, pp. 609-619 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/CMJ.2019.0076-17
Classification : 05C07
Keywords: degree sequence; bigraphic pair; potentially ${\rm SB}_{s+s', t+t'}$-bigraphic pair 
@article{10_21136_CMJ_2019_0076_17,
     author = {Yin, Jian-Hua and Li, Jia-Yun and Du, Jin-Zhi and Li, Hai-Yan},
     title = {Bigraphic pairs with a realization containing a split bipartite-graph},
     journal = {Czechoslovak Mathematical Journal},
     pages = {609--619},
     year = {2019},
     volume = {69},
     number = {3},
     doi = {10.21136/CMJ.2019.0076-17},
     mrnumber = {3989269},
     zbl = {07088807},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2019.0076-17/}
}
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
SP  - 609
EP  - 619
VL  - 69
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2019.0076-17/
DO  - 10.21136/CMJ.2019.0076-17
LA  - en
ID  - 10_21136_CMJ_2019_0076_17
ER  - 
%0 Journal Article
%A Yin, Jian-Hua
%A Li, Jia-Yun
%A Du, Jin-Zhi
%A Li, Hai-Yan
%T Bigraphic pairs with a realization containing a split bipartite-graph
%J Czechoslovak Mathematical Journal
%D 2019
%P 609-619
%V 69
%N 3
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2019.0076-17/
%R 10.21136/CMJ.2019.0076-17
%G en
%F 10_21136_CMJ_2019_0076_17
Yin, Jian-Hua; Li, Jia-Yun; Du, Jin-Zhi; Li, Hai-Yan. Bigraphic pairs with a realization containing a split bipartite-graph. Czechoslovak Mathematical Journal, Tome 69 (2019) no. 3, pp. 609-619. doi: 10.21136/CMJ.2019.0076-17

[1] Erdős, P., Gallai, T.: Graphs with prescribed degrees of vertices. Mat. Lapok 11 Hungarian (1961), 264-274. | JFM

[2] Ferrara, M., Jacobson, M., Schmitt, J., Siggers, M.: Potentially {$H$}-bigraphic sequences. Discuss. Math., Graph Theory 29 (2009), 583-596. | DOI | MR | JFM

[3] Gale, D.: A theorem on flows in networks. Pac. J. Math. 7 (1957), 1073-1082. | DOI | MR | JFM

[4] Garg, A., Goel, A., Tripathi, A.: Constructive extensions of two results on graphic sequences. Discrete Appl. Math. 159 (2011), 2170-2174. | DOI | MR | JFM

[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 | JFM

[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 | MR | JFM

[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 | MR | JFM

[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 | MR | JFM

[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 | MR | JFM

[12] Yin, J.-H.: A note on potentially {$K_{s,t}$}-bigraphic pairs. Util. Math. 100 (2016), 407-410. | DOI | MR | JFM

[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 | MR | JFM

Cité par Sources :