Minimizer Graphs for a Class of Extremal Problems
Ismailescu, Dan (2002) Minimizer Graphs for a Class of Extremal Problems. Technical Report. Hofstra University.
Full text available as:
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.
Repository Staff Only: edit this item