On the Maximum Weight of a Sparse Connected Graph of Given Order and Size |
| |
Authors: | Mirko Horňák Stanislav Jendrol’ Ingo Schiermeyer |
| |
Institution: | 1.Institute of Mathematics,P.J. ?afárik University,Ko?ice,Slovakia;2.Institut für Diskrete Mathematik und Algebra,Technische Universit?t Bergakademie Freiberg,Freiburg,Germany |
| |
Abstract: | The weight of an edge of a graph is defined to be the sum of degrees of vertices incident to the edge. The weight of a graph G is the minimum of weights of edges of G. Jendrol’ and Schiermeyer (Combinatorica 21:351–359, 2001) determined the maximum weight of a graph having n vertices and m edges, thus solving a problem posed in 1990 by Erd?s. The present paper is concerned with a modification of the mentioned problem, in which involved graphs are connected and of size \(m\le \left( {\begin{array}{c}n\\ 2\end{array}}\right) -\left( {\begin{array}{c}\lceil n/2\rceil \\ 2\end{array}}\right) \). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|