Potentially H-bigraphic sequences
Michael J. Ferrara, Michael S. Jacobson, John R. Schmitt, Mark Siggers · Discussiones Mathematicae Graph Theory · 2009
Abstract. We extend the notion of a potentially H-graphic sequence as fol-lows. Let A and B be nonnegative integer sequences. The sequence pair S = (A,B) is said to be bigraphic if there is some bipartite graph G = (X ∪ Y, E) such that A and B are the degrees of the vertices in X and Y, respectively. If S is a bigraphic pair, let σ(S) denote the sum of the terms in A. Given a bigraphic pair S, and a fixed bipartite graph H, we say that S is potentially H-bigraphic if there is some realization of S containing H as a subgraph. We define σ(H,m, n) to be the minimum integer k such that every bigraphic pair S = (A,B) with |A | = m, |B | = n and σ(S) ≥ k is poten-tially H-bigraphic. In this paper, we determine σ(Ks,t, m, n), σ(Pt,m, n) and σ(C2t, m, n). 1.