TY - JOUR

T1 - Potentially H-bigraphic sequences

AU - Ferrara, Michael

AU - Jacobson, Michael

AU - Schmitt, John

AU - Siggers, Mark

PY - 2009

Y1 - 2009

N2 - We extend the notion of a potentially H-graphic sequence as follows. 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 potentially H-bigraphic. In this paper, we determine σ(Ks,t, m,n); σ(Pt; m, n) and σ(C2t, m, n).

AB - We extend the notion of a potentially H-graphic sequence as follows. 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 potentially H-bigraphic. In this paper, we determine σ(Ks,t, m,n); σ(Pt; m, n) and σ(C2t, m, n).

KW - Bipartite graph

KW - Degree sequence

KW - Potential number

UR - http://www.scopus.com/inward/record.url?scp=77956635525&partnerID=8YFLogxK

U2 - 10.7151/dmgt.1466

DO - 10.7151/dmgt.1466

M3 - Article

AN - SCOPUS:77956635525

SN - 1234-3099

VL - 29

SP - 583

EP - 596

JO - Discussiones Mathematicae - Graph Theory

JF - Discussiones Mathematicae - Graph Theory

IS - 3

ER -