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:

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
163 Kb

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.

Item Type:	Monograph (Technical Report)
Uncontrolled Keywords:	combinatorics, graph theory, vertex degrees
Subjects:	Q Science > Q Science (General) Q Science > QA Mathematics
ID Code:	37
Deposited By:	Admin HofPrints
Deposited On:	03 January 2006

Repository Staff Only: edit this item