JIPAM

Sum of Squares of Degrees in a Graph  
 
  Authors: Bernardo M. Ábrego, Silvia Fernández-Merchant, Michael G. Neubauer, William Watkins,  
  Keywords: Graph, Degree sequence, Threshold graph, Pell's Equation, Partition, Density.  
  Date Received: 18/09/2008  
  Date Accepted: 19/06/2009  
  Subject Codes:

05C07, 05C35.

  
  Editors: Chi-Kwong Li,  
 
  Abstract:

Let $ mathcal{G}(v,e)$ be the set of all simple graphs with $ v$ vertices and $ e$ edges and let $ P_2(G)=sum d_i^2$ denote the sum of the squares of the degrees, , of the vertices of $ G$.

It is known that the maximum value of $ P_2(G)$ for $ G in mathcal{G}(v,e)$ occurs at one or both of two special graphs in $ mathcal{G}(v,e)$--the quasi-star graph or the quasi-complete graph. For each pair $ (v,e)$, we determine which of these two graphs has the larger value of $ P_2(G)$. We also determine all pairs $ (v,e)$ for which the values of $ P_2(G)$ are the same for the quasi-star and the quasi-complete graph. In addition to the quasi-star and quasi-complete graphs, we find all other graphs in $ mathcal{G}(v,e)$ for which the maximum value of $ P_2(G)$ is attained. Density questions posed by previous authors are examined. ;


This article was printed from JIPAM
http://jipam.vu.edu.au

The URL for this article is:
http://jipam.vu.edu.au/article.php?sid=1120