A CONSTRUCTIVE EXTENSION OF THE CHARACTERIZATION ON POTENTIALLY Ks,t-BIGRAPHIC PAIRS

作者：Guo, Ji-Yun; Yin, Jian-Hua^*

来源：Discussiones Mathematicae - Graph Theory, 2017, 37(1): 251-259.

DOI：10.7151/dmgt.1928

• degree sequence
• bigraphic pair
• potentially K-s,K-t-bigraphic pair

Let K-s,K-t be the complete bipartite graph with partite sets of size s and t. Let L-1 = ( [a(1), b(1),..., [a(m), b(m)]) and L-2 = ([c(1), d(1)],..., [c(n), d(n)]) be two sequences of intervals consisting of nonnegative integers with a(1) a(2) ... am and c(1) c(2) ... c(n). We say that L = (L-1; L-2) is potentially K-s,K-t (resp. A(s,t))-bigraphic if there is a simple bipartite graph G with partite sets X = {x(1),..., x(m)} and Y = {y(1),..., y(n)} such that a(i) <= d(G)(x(i)) <= b(i) for 1 <= i <= m, c(i) <= d(G)(y(i)) <= d(i) for 1 <= i <= n and G contains K-s,K-t as a subgraph (resp. the induced subgraph of {x(1),..., x(s), y(1),..., y(t)} in G is a K-s,K-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,K-t-bigraphic if b(1) b(2) ... b(m) and d(1) d(2) ... d(m). 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).

• 出版日期2017-2
• 单位海南大学