A Constructive Extension of the Characterization on Potentially K<sub>s,t</sub>-Bigraphic Pairs

Guo, Ji-Yun; Yin, Jian-Hua

Geodesic

Parcourir par

A Constructive Extension of the Characterization on Potentially K_s,t-Bigraphic Pairs

Guo, Ji-Yun ; Yin, Jian-Hua

Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 1, pp. 251-259

Voir la notice de l'article provenant de la source Library of Science

Résumé

Let K_s,t be the complete bipartite graph with partite sets of size s and t. Let L₁ = ([a₁, b₁], . . ., [a_m, b_m]) and L₂ = ([c₁, d₁], . . ., [c_n, d_n]) be two sequences of intervals consisting of nonnegative integers with a₁ ≥ a₂ ≥ . . . ≥ a_m and c₁ ≥ c₂ ≥ . . . ≥ c_n. We say that L = (L₁; L₂) is potentially K_s,t (resp. A_s,t)-bigraphic if there is a simple bipartite graph G with partite sets X = x₁, . . ., x_m and Y = y₁, . . ., y_n such that a_i ≤ dG(x_i) ≤ bi for 1 ≤ i ≤ m, c_i ≤ d_G(y_i) ≤ d_i for 1 ≤ i ≤ n and G contains K_s,t as a subgraph (resp. the induced subgraph of x₁, . . ., x_s, y₁, . . ., y_t in G is a K_s,t). In this paper, we give a characterization of L that is potentially A_s,t-bigraphic. As a corollary, we also obtain a characterization of L that is potentially K_s,t-bigraphic if b₁ ≥ b₂ ≥ . . . ≥ b_m and d₁ ≥ d₂ ≥ . . . ≥ d_n. This is a constructive extension of the characterization on potentially K_s,t-bigraphic pairs due to Yin and Huang (Discrete Math. 312 (2012) 1241–1243).

Keywords: degree sequence, bigraphic pair, potentially K s,t -bigraphic pair

@article{DMGT_2017_37_1_a17,
     author = {Guo, Ji-Yun and Yin, Jian-Hua},
     title = {A {Constructive} {Extension} of the {Characterization} on {Potentially} {K\protect\textsubscript{s,t}-Bigraphic} {Pairs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {251--259},
     publisher = {mathdoc},
     volume = {37},
     number = {1},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a17/}
}

TY  - JOUR
AU  - Guo, Ji-Yun
AU  - Yin, Jian-Hua
TI  - A Constructive Extension of the Characterization on Potentially Ks,t-Bigraphic Pairs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 251
EP  - 259
VL  - 37
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a17/
LA  - en
ID  - DMGT_2017_37_1_a17
ER  -

%0 Journal Article
%A Guo, Ji-Yun
%A Yin, Jian-Hua
%T A Constructive Extension of the Characterization on Potentially Ks,t-Bigraphic Pairs
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 251-259
%V 37
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a17/
%G en
%F DMGT_2017_37_1_a17

Guo, Ji-Yun; Yin, Jian-Hua. A Constructive Extension of the Characterization on Potentially K_s,t-Bigraphic Pairs. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 1, pp. 251-259. http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a17/