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

Abstract

top
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 2 t , m , n ) .

How to cite

top

Michael 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. [1] F. Chung and R. Graham, Erdös on Graphs (A K Peters Ltd, 1998). 
  2. [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. [3] D. Gale, A theorem on flows in networks, Pac. J. Math. 7 (1957) 1073-1082. Zbl0087.16303
  4. [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. [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. [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. [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. [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. [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. [10] R. Luo, On potentially Cₖ-graphic sequences, Ars Combin. 64 (2002) 301-318. Zbl1071.05520
  11. [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. [12] K. Zarankiewicz, Problem P 101, Colloq. Math. 2 (1951) 301. 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.