Geodesic
Potentially H-bigraphic sequences
Discussiones Mathematicae. Graph Theory, Tome 29 (2009) no. 3, pp. 583-596.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: degree sequence, bipartite graph, potential number 
@article{DMGT_2009_29_3_a9,
     author = {Ferrara, Michael and Jacobson, Michael and Schmitt, John and Siggers, Mark},
     title = {Potentially {H-bigraphic} sequences},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {583--596},
     publisher = {mathdoc},
     volume = {29},
     number = {3},
     year = {2009},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2009_29_3_a9/}
}
TY  - JOUR
AU  - Ferrara, Michael
AU  - Jacobson, Michael
AU  - Schmitt, John
AU  - Siggers, Mark
TI  - Potentially H-bigraphic sequences
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2009
SP  - 583
EP  - 596
VL  - 29
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2009_29_3_a9/
LA  - en
ID  - DMGT_2009_29_3_a9
ER  - 
%0 Journal Article
%A Ferrara, Michael
%A Jacobson, Michael
%A Schmitt, John
%A Siggers, Mark
%T Potentially H-bigraphic sequences
%J Discussiones Mathematicae. Graph Theory
%D 2009
%P 583-596
%V 29
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2009_29_3_a9/
%G en
%F DMGT_2009_29_3_a9
Ferrara, Michael; Jacobson, Michael; Schmitt, John; Siggers, Mark. Potentially H-bigraphic sequences. Discussiones Mathematicae. Graph Theory, Tome 29 (2009) no. 3, pp. 583-596. http://geodesic.mathdoc.fr/item/DMGT_2009_29_3_a9/

[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ₖ-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ₖ-graphical sequences, J. Graph Theory 29 (1998) 63-72, doi: 10.1002/(SICI)1097-0118(199810)29:263::AID-JGT2>3.0.CO;2-A

[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.

[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ₖ-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.