PDF

Discussiones Mathematicae Graph Theory 33(1) (2013) 147-165
DOI: https://doi.org/10.7151/dmgt.1674

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

On maximum weight of a bipartite graph
of given order and size

Mirko Horňák Stanislav Jendrol' Institute of Mathematics P.J. Šafárik University Jesenná 5, 04001 Košice, Slovakia

Ingo Schiermeyer Institut für Diskrete Mathematik und Algebra Technische Universität Bergakademie Freiberg 09596 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.

Received 2 February 2012
Revised 8 January 2012
Accepted 9 January 2012