Sum of squares of degrees in a graph

Abstract

Let $\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, $d_1,>...,d_v$, of the vertices of $G$. It is known that the maximum value of $P_2(G)$ for $G \in \G(v,e)$ occurs at one or both of two special graphs in $\G(v,e)$--the \qs graph or the \qc 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 \qs and the \qc graph. In addition to the \qs and \qc graphs, we find all other graphs in $\G(v,e)$ for which the maximum value of $P_2(G)$ is attained. Density questions posed by previous authors are examined.

40 pages, 11 figures. Updated introduction, a minor issue on the definition of Quasi-complete graphs was fixed, and a couple of references were added

Cited by in corpus (7)

• The Complex Hierarchical Topology of EEG Functional Connectivity
• Improved enumeration of simple topological graphs
• Mathematical and Algorithmic Analysis of Network and Biological Data
• Maximum star densities
• The Autodidactic Universe
• Subproduct systems and Cartesian systems; new results on factorial languages and their relations with other areas
• On graphs having minimal fourth adjacency coefficient