Sum of squares of degrees in a graph

Authors

Publication date 23 November 2009

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Abstract: Let

G (v, e)

be the set of all simple graphs with

v

vertices and

e

edges and let

P_{2} (G) = s u m 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 i n 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.

Recommendations

Cited in

(24)

This page was built for publication: Sum of squares of degrees in a graph