On Maximum Weight of a Bipartite Graph of Given Order and Size

Mirko Horňák; Stanislav Jendrol’; Ingo Schiermeyer

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 1, page 147-165
  • ISSN: 2083-5892

Abstract

top
The weight of an edge xy of a graph is defined to be the sum of degrees of the vertices x and y. The weight of a graph G is the minimum of weights of edges of G. More than twenty years ago Erd˝os was interested in finding the maximum weight of a graph with n vertices and m edges. This paper presents a complete solution of a modification of the above problem in which a graph is required to be bipartite. It is shown that there is a function w*(n,m) such that the optimum weight is either w*(n,m) or w*(n,m) + 1.

How to cite

top

Mirko Horňák, Stanislav Jendrol’, and Ingo Schiermeyer. "On Maximum Weight of a Bipartite Graph of Given Order and Size." Discussiones Mathematicae Graph Theory 33.1 (2013): 147-165. <http://eudml.org/doc/267989>.

@article{MirkoHorňák2013,
abstract = {The weight of an edge xy of a graph is defined to be the sum of degrees of the vertices x and y. The weight of a graph G is the minimum of weights of edges of G. More than twenty years ago Erd˝os was interested in finding the maximum weight of a graph with n vertices and m edges. This paper presents a complete solution of a modification of the above problem in which a graph is required to be bipartite. It is shown that there is a function w*(n,m) such that the optimum weight is either w*(n,m) or w*(n,m) + 1.},
author = {Mirko Horňák, Stanislav Jendrol’, Ingo Schiermeyer},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {weight of an edge; weight of a graph; bipartite graph.; bipartite graph},
language = {eng},
number = {1},
pages = {147-165},
title = {On Maximum Weight of a Bipartite Graph of Given Order and Size},
url = {http://eudml.org/doc/267989},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Mirko Horňák
AU - Stanislav Jendrol’
AU - Ingo Schiermeyer
TI - On Maximum Weight of a Bipartite Graph of Given Order and Size
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 1
SP - 147
EP - 165
AB - The weight of an edge xy of a graph is defined to be the sum of degrees of the vertices x and y. The weight of a graph G is the minimum of weights of edges of G. More than twenty years ago Erd˝os was interested in finding the maximum weight of a graph with n vertices and m edges. This paper presents a complete solution of a modification of the above problem in which a graph is required to be bipartite. It is shown that there is a function w*(n,m) such that the optimum weight is either w*(n,m) or w*(n,m) + 1.
LA - eng
KW - weight of an edge; weight of a graph; bipartite graph.; bipartite graph
UR - http://eudml.org/doc/267989
ER -

References

top
  1. [1] O.V. Borodin, Computing light edges in planar graphs, in: Topics in Combinatorics and Graph Theory, R. Bodendiek and R. Henn (Ed(s)), (Physica-Verlag, Heidelberg, 1990) 137-144. 
  2. [2] H. Enomoto and K. Ota, Connected subgraphs with small degree sum in 3-connected planar graphs, J. Graph Theory 30 (1999) 191-203. doi:10.1002/(SICI)1097-0118(199903)30:3h191::AID-JGT4i3.0.CO;2-X[Crossref] Zbl0916.05020
  3. [3] I. Fabrici and S. Jendrol’, Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs Combin. 13 (1997) 245-250. Zbl0891.05025
  4. [4] B. Grünbaum, Acyclic colorings of planar graphs, Israel J. Math. 14 (1973) 390-408. doi:10.1007/BF02764716[Crossref] Zbl0265.05103
  5. [5] J. Ivančo, The weight of a graph, in: Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity, J. Neˇsetˇril and M. Fiedler (Ed(s)), (North- Holland, Amsterdam, 1992) 113-116. Zbl0773.05066
  6. [6] J. Ivančo and S. Jendrol’, On extremal problems concerning weights of edges of graphs, in: Sets, Graphs and Numbers, G. Hal´asz, L. Lov´asz, D. Mikl´os and T. Sz˝onyi (Ed(s)), (North-Holland, Amsterdam, 1992) 399-410. Zbl0790.05045
  7. [7] E. Jucovič, Strengthening of a theorem about 3-polytopes, Geom. Dedicata 13 (1974) 233-237. doi:10.1007/BF00183214 Zbl0297.52006
  8. [8] S. Jendrol’ and I. Schiermeyer, On a max-min problem concerning weights of edges, Combinatorica 21 (2001) 351-359. doi:10.1007/s004930100001[Crossref] Zbl1012.05091
  9. [9] S. Jendrol’, M. Tuhársky and H.-J. Voss, A Kotzig type theorem for large maps on surfaces, Tatra Mt. Math. Publ. 27 (2003) 153-162. Zbl1062.05044
  10. [10] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat.-Fyz. ˇ Casopis. Slovensk. Akad. Vied 5 (1955) 111-113. 
  11. [11] J. Zaks, Extending Kotzig’s theorem, Israel J. Math. 45 (1983) 281-296. doi:10.1007/BF02804013[Crossref] Zbl0524.05031

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.