Minimizer graphs for a class of extremal problems
Dan Ismailescu, Dan Stefanica · Journal of Graph Theory · 2002
Abstract We consider the family of graphs with a fixed number of vertices and edges. Among all these graphs, we are looking for those minimizing the sum of the square roots of the vertex degrees. We prove that there is a unique such graph, which consists of the largest possible complete subgraph plus only one other non‐isolated vertex. The same result is proven for any power of the vertex‐degrees less than one half. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 230–240, 2002; DOI 10.1002/jgt.10025