Dedicated to Mietek Borowiecki on the occasion of his seventieth birthday.

## On maximum weight of a bipartite graphof given order and size

 Mirko HorňákStanislav Jendrol' Institute of MathematicsP.J. Šafárik UniversityJesenná 5, 04001 Košice, Slovakia Ingo Schiermeyer Institut für Diskrete Mathematik und Algebra Technische Universität Bergakademie Freiberg09596 Freiberg, Germany

## 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 Erdos 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.

Keywords: weight of an edge, weight of a graph, bipartite graph

2010 Mathematics Subject Classification: 05C35.

## References

 [1] O.V. Borodin, Computing light edges in planar graphs, in: Topics in Combinatorics and Graph Theory, ed(s), R. Bodendiek and R. Henn Physica-Verlag, Heidelberg, 1990) 137--144. [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:3<191::AID-JGT4>3.0.CO;2-X. [3] I. Fabrici and S. Jendrol', Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs Combin. 13 (1997) 245--250. [4] B. Grünbaum, Acyclic colorings of planar graphs, Israel J. Math. 14 (1973) 390--408, doi: 10.1007/BF02764716 . [5] J. Ivančo, The weight of a graph, in: Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity, ed(s), J. Nešetřil and M. Fiedler North-Holland, Amsterdam, 1992) 113--116. [6] J. Ivančo and S. Jendrol', On extremal problems concerning weights of edges of graphs, in: Sets, Graphs and Numbers, ed(s), G. Halász, L. Lovász, D. Miklós and T. Szönyi North-Holland, Amsterdam, 1992) 399--410. [7] E. Jucovič, Strengthening of a theorem about 3-polytopes, Geom. Dedicata 13 (1974) 233--237, doi: 10.1007/BF00183214. [8] S. Jendrol' and I. Schiermeyer, On a max-min problem concerning weights of edges, Combinatorica 21 (2001) 351--359, doi: 10.1007/s004930100001. [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. [10] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat.-Fyz. Časopis. Slovensk. Akad. Vied 5 (1955) 111--113. [11] J. Zaks, Extending Kotzig's theorem, Israel J. Math. 45 (1983) 281--296, doi: 10.1007/BF02804013.