A Constructive Extension of the Characterization on PotentiallyK s , t -Bigraphic Pairs

Ji-Yun Guo, and Jian-Hua Yin. "A Constructive Extension of the Characterization on PotentiallyK s , t -Bigraphic Pairs." Discussiones Mathematicae Graph Theory 37.1 (2017): 251-259. <http://eudml.org/doc/288005>.

@article{Ji2017,
abstract = {Let Ks,t be the complete bipartite graph with partite sets of size s and t. Let L1 = ([a1, b1], . . . , [am, bm]) and L2 = ([c1, d1], . . . , [cn, dn]) be two sequences of intervals consisting of nonnegative integers with a1 ≥ a2 ≥ . . . ≥ am and c1 ≥ c2 ≥ . . . ≥ cn. We say that L = (L1; L2) is potentially Ks,t (resp. As,t)-bigraphic if there is a simple bipartite graph G with partite sets X = \{x1, . . . , xm\} and Y = \{y1, . . . , yn\} such that ai ≤ dG(xi) ≤ bi for 1 ≤ i ≤ m, ci ≤ dG(yi) ≤ di for 1 ≤ i ≤ n and G contains Ks,t as a subgraph (resp. the induced subgraph of \{x1, . . . , xs, y1, . . . , yt\} in G is a Ks,t). In this paper, we give a characterization of L that is potentially As,t-bigraphic. As a corollary, we also obtain a characterization of L that is potentially Ks,t-bigraphic if b1 ≥ b2 ≥ . . . ≥ bm and d1 ≥ d2 ≥ . . . ≥ dn. This is a constructive extension of the characterization on potentially Ks,t-bigraphic pairs due to Yin and Huang (Discrete Math. 312 (2012) 1241–1243).},
author = {Ji-Yun Guo, Jian-Hua Yin},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {degree sequence; bigraphic pair; potentially Ks,t-bigraphic pair; potentially -bigraphic pair},
language = {eng},
number = {1},
pages = {251-259},
title = {A Constructive Extension of the Characterization on PotentiallyK s , t -Bigraphic Pairs},
url = {http://eudml.org/doc/288005},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Ji-Yun Guo
AU - Jian-Hua Yin
TI - A Constructive Extension of the Characterization on PotentiallyK s , t -Bigraphic Pairs
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 1
SP - 251
EP - 259
AB - Let Ks,t be the complete bipartite graph with partite sets of size s and t. Let L1 = ([a1, b1], . . . , [am, bm]) and L2 = ([c1, d1], . . . , [cn, dn]) be two sequences of intervals consisting of nonnegative integers with a1 ≥ a2 ≥ . . . ≥ am and c1 ≥ c2 ≥ . . . ≥ cn. We say that L = (L1; L2) is potentially Ks,t (resp. As,t)-bigraphic if there is a simple bipartite graph G with partite sets X = {x1, . . . , xm} and Y = {y1, . . . , yn} such that ai ≤ dG(xi) ≤ bi for 1 ≤ i ≤ m, ci ≤ dG(yi) ≤ di for 1 ≤ i ≤ n and G contains Ks,t as a subgraph (resp. the induced subgraph of {x1, . . . , xs, y1, . . . , yt} in G is a Ks,t). In this paper, we give a characterization of L that is potentially As,t-bigraphic. As a corollary, we also obtain a characterization of L that is potentially Ks,t-bigraphic if b1 ≥ b2 ≥ . . . ≥ bm and d1 ≥ d2 ≥ . . . ≥ dn. This is a constructive extension of the characterization on potentially Ks,t-bigraphic pairs due to Yin and Huang (Discrete Math. 312 (2012) 1241–1243).
LA - eng
KW - degree sequence; bigraphic pair; potentially Ks,t-bigraphic pair; potentially -bigraphic pair
UR - http://eudml.org/doc/288005
ER -