Geodesic
On Maximum Weight of a Bipartite Graph of Given Order and Size
Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 1, pp. 147-165

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: weight of an edge, weight of a graph, bipartite graph 
@article{DMGT_2013_33_1_a12,
     author = {Hor\v{n}\'ak, Mirko and Jendrol{\textquoteright}, Stanislav and Schiermeyer, Ingo},
     title = {On {Maximum} {Weight} of a {Bipartite} {Graph} of {Given} {Order} and {Size}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {147--165},
     publisher = {mathdoc},
     volume = {33},
     number = {1},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a12/}
}
TY  - JOUR
AU  - Horňák, Mirko
AU  - Jendrol’, Stanislav
AU  - Schiermeyer, Ingo
TI  - On Maximum Weight of a Bipartite Graph of Given Order and Size
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2013
SP  - 147
EP  - 165
VL  - 33
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a12/
LA  - en
ID  - DMGT_2013_33_1_a12
ER  - 
%0 Journal Article
%A Horňák, Mirko
%A Jendrol’, Stanislav
%A Schiermeyer, Ingo
%T On Maximum Weight of a Bipartite Graph of Given Order and Size
%J Discussiones Mathematicae. Graph Theory
%D 2013
%P 147-165
%V 33
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a12/
%G en
%F DMGT_2013_33_1_a12
Horňák, Mirko; Jendrol’, Stanislav; Schiermeyer, Ingo. On Maximum Weight of a Bipartite Graph of Given Order and Size. Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 1, pp. 147-165. http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a12/