DMGT

Discussiones Mathematicae Graph Theory 29(3) (2009) 583-596
DOI: https://doi.org/10.7151/dmgt.1466

POTENTIALLY H-BIGRAPHIC SEQUENCES

Michael Ferrara
University of Colorado at Denver
e-mail: michael.ferrara@ucdenver.edu
Michael Jacobson
University of Colorado at Denver
e-mail: michael.jacobson@ucdenver.edu
John Schmitt
Middlebury College
e-mail: jschmitt@middlebury.edu
Mark Siggers
Kyungpook National University
e-mail: mhsiggers@knu.ac.kr

Abstract

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 σ(K_s,t,m,n), σ(P_t,m,n) and σ(C_2t,m,n).

Keywords: degree sequence, bipartite graph, potential number.

2000 Mathematics Subject Classification: 05C07, 05C35.

References

[1]	F. Chung and R. Graham, Erdös on Graphs (A K Peters Ltd, 1998).
[2]	P. Erdös, M.S. Jacobson and J. Lehel, Graphs Realizing the Same Degree Sequence and their Respective Clique Numbers, in: Graph Theory, Combinatorics and Applications, Vol. I, ed. Alavi, Chartrand, Oellerman and Schwenk (1991) 439-449.
[3]	D. Gale, A theorem on flows in networks, Pac. J. Math. 7 (1957) 1073-1082.
[4]	R.J. Gould, M.S. Jacobson and J. Lehel, Potentially G-graphic degree sequences, in: Combinatorics, Graph Theory, and Algorithms Vol. I, eds. Alavi, Lick and Schwenk (New York: Wiley & Sons, Inc., 1999) 387-400.
[5]	C. Lai, The smallest degree sum that yields potentially C_k-graphical sequence, J. Combin. Math. Combin. Computing 49 (2004) 57-64.
[6]	J. Li and Z. Song, The smallest degree sum that yields potentially P_k-graphical sequences, J. Graph Theory 29 (1998) 63-72, doi: 10.1002/(SICI)1097-0118(199810)29:2<63::AID-JGT2>3.0.CO;2-A.
[7]	J. Li, Z. Song and R. Luo, The Erdös-Jacobson-Lehel conjecture on potentially P_k-graphic sequences is true, Science in China (A) 41 (1998) 510-520, doi: 10.1007/BF02879940.
[8]	J. Li and J. Yin, The smallest degree sum that yields potentially K_r,r-graphic sequences, Science in China (A) 45 (2002) 694-705.
[9]	J. Li and J. Yin, An extremal problem on potentially K_r,s-graphic sequences, Discrete Math. 260 (2003) 295-305, doi: 10.1016/S0012-365X(02)00765-3.
[10]	R. Luo, On potentially C_k-graphic sequences, Ars Combin. 64 (2002) 301-318.
[11]	H.J. Ryser, Combinatorial properties of matrices of zeros and ones, Canad. J. Math. 9 (1957) 371-377, doi: 10.4153/CJM-1957-044-3.
[12]	K. Zarankiewicz, Problem P 101, Colloq. Math. 2 (1951) 301.

Received 5 June 2008
Accepted 5 September 2008