Discrete Mathematics 306 (2006) 1959 – 1964

www.elsevier.com/locate/disc

Note
Sums of powers of the degrees of a graph!
Sebastian M. Cioabă1
Department of Mathematics, Queen’s University at Kingston, Ont. K7L 3N6, Canada

Received 27 October 2005; received in revised form 23 February 2006; accepted 28 March 2006
Available online 14 June 2006

Abstract
For a graph G and k a real number, we consider the sum of the kth powers of the degrees of the vertices of G. We present some
general bounds on this sum for various values of k.
© 2006 Elsevier B.V. All rights reserved.

MSC: 05C07
Keywords: Degree powers; Bounds

1. Introduction
!
Let d(u) be the degree of the vertex u in the graph G and let !k (G) = x∈V (G) d
k (x). Obviously, !
0 (G) = |V (G)|
and !1 (G) = 2|E(G)|. In [8], Székely et al. showed that

!k (G) !(!1/k (G))k , (1)

for every integer k "1.

De Caen proved the following inequality in [3]:
" #
2e
!2 (G) !e +n−2 , (2)
n−1
where n is the order and e is the size of the graph G. This bound was generalized to hypergraphs by Bey in [1] and
improved by Das in [2]. De Caen’s inequality was also used by Li and Pan in [6] to provide an upper bound on the
largest eigenvalue of the Laplacian of a graph. We discuss the Li–Pan bound in Section 6. The kth moment of the degree
sequence of a graph G of order n is "k (G) = !k (G)/n. Sharp bounds for the moments of the degree sequences of
monotone families of graphs were obtained by Füredi and Kündgen in [4].
In this paper, we prove a general upper bound on !k (G) for k real number. The main result is contained in Section
3. When k = 2, we obtain the two results of Das that improve De Caen’s bound.

! Research partially supported by an Ontario Graduate Scholarship and an NSERC Postdoctoral Fellowship.
1 Present address: Department of Mathematics, University of California, San Diego, La Jolla, CA 92093-0112, USA.
E-mail address: [email protected].

0012-365X/$ - see front matter © 2006 Elsevier B.V. All rights reserved.
doi:10.1016/j.disc.2006.03.054
1960 S.M. Cioabă / Discrete Mathematics 306 (2006) 1959 – 1964

2. Preliminaries

We denote by Bn,t the graph on n vertices with exactly t vertices of degree n − 1 and the remaining of n − t vertices
forming an independent set. Notice that Bn,1 = K1,n−1 and Bn,n = Kn . The maximum degree of a graph G will be
denoted by #(G) and the minimum degree by $(G). We denote by mk (u) the average of the kth powers of the degrees
of the vertices v adjacent to u and by pk (u) the average of the kth powers of the degrees of the vertices w #= u that are
not adjacent to u. Then
!k (G) = d k (u) + d(u)mk (u) + (n − 1 − d(u))pk (u),
for each vertex u in G. It follows that
d k (u) + (n − 1)mk (u) = !k (G) + (n − 1 − d(u))(mk (u) − pk (u))
which implies
" #
d k (u) !k (G) 1
+ mk (u) = + 1− d(u) (mk (u) − pk (u)). (3)
n−1 n−1 n−1
We will use Eq. (3) to obtain upper bounds on !k (G).

Lemma 1. If G is a graph and k a real number, then

$
!k+1 (G) = d(u)mk (u). (4)
u∈V (G)

Proof. Using a double summation, we get

$ $ $
d(u)mk (u) = d k (v)
u∈V (G) u∈V (G) v∼u
$ $ $
= d k (v) = d k+1 (v) = !k+1 (G). #
v∈V (G) u∼v v∈V (G)

Using Eq. (3), we obtain the following result.

Lemma 2. Let G be a graph and k a positive number. Then

" #
d k (u) !k (G) 1
+ mk (u) ! + 1− d(u) (#k (G) − $k (G)), (5)
n−1 n−1 n−1
for each u ∈ V (G). Equality holds if and only if either d(u) = n − 1 or d(v) = #(G) for each v adjacent to u and
d(w) = $(G) for each w #= u non-adjacent to u.

Proof. Obviously, 1 − d(u)/(n − 1)"0 with equality if and only if d(u) = n − 1. Because k > 0, it follows
that mk (u)−pk (u) !#k (G)−$k (G), for each u ∈ V (G). These two relations together with Eq. (3) imply the desired in-
equality. Equality holds iff d(u) = n − 1 or mk (u) = #k (G) and pk (u) = $k (G). The second
condition is equivalent to d(v) = #(G) for each v adjacent to u and d(w) = $(G) for each w # = u non-adjacent
to u. #

3. Main results

Theorem 3. If G is a connected graph and k a positive number, then

2e # k − $k
!k+1 (G)! (!k (G) + (n − 1)(#k − $k )) − !2 (G), (6)
n n
where # = #(G), $ = $(G) and e = |E(G)|. Equality holds if and only if G = Bn,t for some 1 !t !n or G is regular.
 S.M. Cioabă / Discrete Mathematics 306 (2006) 1959 – 1964 1961

Proof. Using (5), we get

d k (u) !k (G) # k − $k
+ mk (u) ! + (#k − $k ) − d(u), (7)
n−1 n−1 n−1
for each u ∈ V (G). Multiplying by d(u), summing over all u ∈ V (G) and using (4), we obtain

2e # k − $k
!k+1 (G)! (!k (G) + (n − 1)(#k − $k )) − !2 (G).
n n
Notice that we have equality in (6) if and only if we have equality in (7) for each u ∈ V (G). It follows that equality
holds if and only if for each u ∈ V (G), we either have d(u) = n − 1 or d(v) = # for v adjacent to u and d(w) = $ for
w #= u non-adjacent to u. Obviously, if G is regular then equality holds.
Assume that equality holds and # > $. We will first show that # = n − 1. Let u ∈ V (G) such that d(u) < n − 1.
Then all the neighbors of u have degree # and all the vertices non-adjacent to u have degree $. If all the vertices v #= u
are adjacent to u, then # = n − 1. Otherwise, because G is connected, there is a vertex w adjacent to a neighbor v of u
such that w is not adjacent to u. Thus, d(w) = $. If # = d(v) < n − 1, then all the neighbors of v (including w) have
degree #, contradiction. Hence, # = n − 1.
Let t be the number of vertices u in G such that d(u) = n − 1. Then the remaining n − t vertices form an independent
set. Suppose vw is an edge with d(v) < n − 1 and d(w) < n − 1. Since d(v) < n − 1, it follows that d(w) = # = n − 1,
contradiction. Hence, G = Bn,t in this case. Finally, it is clear that each graph Bn,t gives equality in (6). This completes
the equality case analysis. #

Remark 4. By Chebyschev’s inequality, we have

2e
!k+1 (G)" !k (G), (8)
n
with equality if and only if G is regular. Thus, the difference between these two bounds on !k+1 (G) is (#k − $k )
(2e(n − 1) − !2 (G))/n which gets smaller when the graph is almost regular.

Remark 5. If k = 1 in (6), we obtain the following inequality:

2e(2e + (n − 1)(# − $))
!2 (G) ! . (9)
n+#−$
This is Theorem 4.2 from [2]. Note that Theorem 4.2 of [2] states that equality holds in (9) if and only if G is regular
or G is the disjoint union of K#+1 with n − # − 1 isolated vertices. This is not correct since equality holds in (9) also
for G = Bn,t when 1 !t !n. Note that inequality (9) implies De Caen’s inequality (2). This is because the left-hand
side of (9) gets larger as # − $ increases and # − $!n − 2.
For k = 1 in Lemma 2, we obtain
2e d(u)
d(u) + m1 (u) ! + (n − 2 − (#(G) − $(G))) + (#(G) − $(G))
n−1 n−1
2e #(G)
! + (n − 2 − (#(G) − $(G))) + (#(G) − $(G)),
n−1 n−1
for each u ∈ V (G). Multiplying by d(u) and summing over all u ∈ V (G), we obtain the following inequality:
" " # #
2e #(G) n−2
!2 (G) !e + (#(G) − $(G)) 1 − + #(G) . (10)
n−1 n−1 n−1
Equality holds if and only if #(G) = n − 1 and $(G) = 1 or G is regular. Inequality (10) is Theorem 4.1 from [2]. It
also implies De Caen’s inequality (2) because # − $!n − 2.

Remark 6. The bounds (9) and (10) are incomparable. If G = Pn , the path on n vertices, then (10) is better than (9).
If G = Wn , the wheel with n spokes, then (9) is better than (10).
1962 S.M. Cioabă / Discrete Mathematics 306 (2006) 1959 – 1964

For k = 2 in Theorem 3, we obtain the following upper bound on the sum of the cubes of the degrees of the vertices
in a connected graph.

Corollary 7. If G is a connected graph, then

2e − (#2 − $2 ) 2e(n − 1)(#2 − $2 )

!3 (G)! !2 (G) + . (11)
n n
Equality holds if and only if G is regular or G = Bn,t for some t with 1!t !n.

Inequalities (11) and (1) (for k = 3) are not comparable. For G = Wn the wheel with n spokes, inequality (1) is better
than (11). For G = Kn,n+1 , inequality (11) is better than (1).

4. A general lower bound on !1/2 (G)

% &
k
In [7], Linial and Rozenman showed that among all graphs G with n vertices and 2 edges, the one that minimizes
!1/2 (G)%is the&union of% K&k and n − k isolated vertices. They conjectured that among all the graphs G with n vertices and
k−1 k
e edges, 2 <e< , the minimum !1/2 (G) is attained precisely for the graph whose only non-trivial component
2
% &
is the graph obtained from Kk−1 by adding one new vertex of degree e − k−1 2 . This conjecture was proved by
Ismailescu and Stefanica in [5].
We present a general bound on !1/2 (G) when G is connected.

Theorem 8. If G is a connected graph, then

' √ √ √ √
8en + ( # − $)2 (n − 1 − 2e/n)2 − ( # − $)(n − 1 − 2e/n)
!1/2 (G) " . (12)
2
Equality holds iff G is regular.
1
Proof. If k = 2 in (6), we get
√ √
2e 2e(n − 1) √ √ #− $
!3/2 (G) ! !1/2 + ( # − $) − !2 (G),
n n n
for any connected graph G. Since !2 (G)"(2e)2 /n (Cauchy–Schwarz) and !3/2 (G)!1/2 (G)"(2e)2 (Cauchy–Schwarz),
it follows that
√ √ " 2e
#
(!1/2 (G))2 + ( # − $) n − 1 − !1/2 (G) − 2en"0.
n
This implies the result stated in the theorem. #

'!The inequality (1) for k = 2 can be regarded also as a general lower bound on !1/2 (G). It states that !1/2 (G)"
2
v∈V (G) d (v), for any graph G. If G is d-regular on n vertices, inequality (12) is always equality, whereas the
√ √
inequality (1) gives a lower bound of d n < n d = !1/2 (G).

5. A general upper bound on !−1

By the Cauchy–Schwarz inequality, we have

n2 n2
!−1 (G)" = ,
!1 (G) 2e
 S.M. Cioabă / Discrete Mathematics 306 (2006) 1959 – 1964 1963

for any graph G. Taking k = −1 in (3), we get

" #
m−1 (u) !−1 (G) d(u)
d −1 (u) + " + 1− ($−1 − #−1 )
n−1 n−1 n−1
for any vertex u ∈ V (G). Thus,
" #
!−1 (G) −1 m−1 (u) # − $ d(u)
!d (u) + + 1− ,
n−1 n−1 !$ n−1
for each vertex u ∈ V (G). Multiplying by d(u) and summing over all u ∈ V (G), we obtain
! " #
2e u∈V (G) d(u)m−1 (u) #−$ $ d(u)
!−1 (G)!n + + d(u) 1 − .
n−1 n−1 !$ n−1
u∈V (G)

Using (4) with k = −1, we deduce that

" #
n2 !−$ $ d(u)
!−1 (G) ! + (n − 1) d(u) 1 −
2e 2e!$ n−1
u∈V (G)
" # " #
n2 1 1 !2 (G)
= + − n−1−
2e $ # 2e
2 " #" #
n 1 1 2e
! + − n−1− .
2e $ # n
Hence, we have proved the following result.

Theorem 9. If G is a connected graph, then

" #" #
n2 $ 1 n2 1 1 2e
! ! + − n−1− ,
2e d(u) 2e $ # n
u∈V (G)

with equality if and only if G is regular or G = K1,n−1 .

6. The Li–Pan inequality on the largest Laplacian eigenvalue of a graph

For a graph G, the Laplacian of G is L(G) = D(G) − A(G), where D = diag(d(u))u∈V (G) and A(G) is the adjacency
matrix of G. The eigenvalues of L(G) are %1 (G)"%2 (G)" · · · "%n (G) = 0. Notice that L(G) + L(Gc ) = nI n − Jn ,
where Gc is the complement of G and Jn is the n by n matrix with all the entries 1. It follows easily that %1 (G)!n, for
any graph G on n vertices.
In [6], Li and Pan used De Caen’s inequality (2) to prove the following upper bound on %1 (G) (see Theorem 3.1. in
[6]).

Theorem 10 (Li–Pan). Let be a G connected graph with n vertices and e edges. Then
√
2e + (n − 2)e(n(n − 1) − 2e)
%1 (G) ! , (13)
n−1
with equality if and only if G is one of Kn and K1,n−1 .

Inequality
√
(13) can be deduced easily without applying de Caen’s inequality. It follows from %1 (G)!n and
n ! 2e+ (n−2)e(n(n−1)−2e)
n−1 . We have already proved the first inequality. The inequality
√
2e + (n − 2)e(n(n − 1) − 2e)
n!
n−1
is equivalent to n − 1 !e. This is true since G is connected.
1964 S.M. Cioabă / Discrete Mathematics 306 (2006) 1959 – 1964

Acknowledgments

I thank David Gregory and the two anonymous referees for their comments and suggestions.

References

[1] C. Bey, An upper bound on the sum of the squares of the degrees in a hypergraph, Discrete Math. 269 (2003) 259–263.
[2] K.Ch. Das, Maximizing the sum of the squares of the degrees of a graph, Discrete Math. 285 (2004) 57–66.
[3] D. de Caen, An upper bound on the sum of the squares of the degrees in a graph, Discrete Math. 185 (1998) 245–248.
[4] Z. Füredi, A. Kündgen, Monotone families have their moments, J. Graph Theory 51 (2006) 37–48.
[5] D. Ismailescu, D. Stefanica, Minimizer graphs for a class of extremal problems, J. Graph Theory 39 (4) (2002) 230–240.
[6] J.S. Li, Y.L. Pan, de Caen’s inequality and bounds on the largest Laplacian eigenvalue of a graph, Linear Algebra Appl. 328 (2001) 153–160.
[7] N. Linial, E. Rozenman, An extremal problem on degree sequences of graphs, Graphs Combin. 18 (2002) 573–582.
[8] L.A. Székely, L.H. Clark, R.C. Entriger, An inequality for degree sequences, Discrete Math. 103 (1992) 293–300.