# 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

## Access Full Article

top## Abstract

top## How to cite

topMirko 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] 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] 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] 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] B. Grünbaum, Acyclic colorings of planar graphs, Israel J. Math. 14 (1973) 390-408. doi:10.1007/BF02764716[Crossref] Zbl0265.05103
- [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] 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] E. Jucovič, Strengthening of a theorem about 3-polytopes, Geom. Dedicata 13 (1974) 233-237. doi:10.1007/BF00183214 Zbl0297.52006
- [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] 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] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat.-Fyz. ˇ Casopis. 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[Crossref] Zbl0524.05031

## NotesEmbed ?

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