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

Mirko Horňák | Zendy; Stanislav Jendrol′ | Zendy; Ingo Schiermeyer | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

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

Author(s) -

Mirko Horňák,

Stanislav Jendrol′,

Ingo Schiermeyer

Publication year - 2013

Publication title -

discussiones mathematicae graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.476

H-Index - 19

eISSN - 2083-5892

pISSN - 1234-3099

DOI - 10.7151/dmgt.1674

Subject(s) - mathematics , combinatorics , bipartite graph , edge transitive graph , graph , complete bipartite graph , graph power , weight function , minimum weight , path graph , discrete mathematics , line graph , statistics

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research