# Potentially H-bigraphic sequences

Michael Ferrara; Michael Jacobson; John Schmitt; Mark Siggers

Discussiones Mathematicae Graph Theory (2009)

- Volume: 29, Issue: 3, page 583-596
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topMichael Ferrara, et al. "Potentially H-bigraphic sequences." Discussiones Mathematicae Graph Theory 29.3 (2009): 583-596. <http://eudml.org/doc/270910>.

@article{MichaelFerrara2009,

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ₜ,m,n) and $σ(C_\{2t\},m,n)$.},

author = {Michael Ferrara, Michael Jacobson, John Schmitt, Mark Siggers},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {degree sequence; bipartite graph; potential number},

language = {eng},

number = {3},

pages = {583-596},

title = {Potentially H-bigraphic sequences},

url = {http://eudml.org/doc/270910},

volume = {29},

year = {2009},

}

TY - JOUR

AU - Michael Ferrara

AU - Michael Jacobson

AU - John Schmitt

AU - Mark Siggers

TI - Potentially H-bigraphic sequences

JO - Discussiones Mathematicae Graph Theory

PY - 2009

VL - 29

IS - 3

SP - 583

EP - 596

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 $σ(K_{s,t},m,n)$, σ(Pₜ,m,n) and $σ(C_{2t},m,n)$.

LA - eng

KW - degree sequence; bipartite graph; potential number

UR - http://eudml.org/doc/270910

ER -

## References

top- [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. Zbl0840.05093
- [3] D. Gale, A theorem on flows in networks, Pac. J. Math. 7 (1957) 1073-1082. Zbl0087.16303
- [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ₖ-graphical sequence, J. Combin. Math. Combin. Computing 49 (2004) 57-64. Zbl1054.05027
- [6] J. Li and Z. Song, The smallest degree sum that yields potentially Pₖ-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 Zbl0919.05058
- [7] J. Li, Z. Song and R. Luo, The Erdös-Jacobson-Lehel conjecture on potentially Pₖ-graphic sequences is true, Science in China (A) 41 (1998) 510-520, doi: 10.1007/BF02879940. Zbl0906.05031
- [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. Zbl1099.05505
- [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. Zbl1017.05055
- [10] R. Luo, On potentially Cₖ-graphic sequences, Ars Combin. 64 (2002) 301-318. Zbl1071.05520
- [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. Zbl0079.01102
- [12] K. Zarankiewicz, Problem P 101, Colloq. Math. 2 (1951) 301.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.