A tight upper bound of spectral radius in terms of degree deviation

Wenqian Zhang · 2024

Read A tight upper bound of spectral radius in terms of degree deviation by Wenqian Zhang (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-01207.txt.

Description

A 2024 arXiv research paper by Wenqian Zhang. Let G G be a graph with n n vertices and m m edges. The spectral radius ρ ⁡ ( G ) \rho(G) of G G is the largest eigenvalue of the adjacency matrix of G G . As is well known, ρ ⁡ ( G ) ≥ 2 ​ m n \rho(G)\geq\frac{2m}{n} with equality if and only if G G is regular.

Catalog record

CREATORWenqian Zhang
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE7 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2411-01207

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A tight upper bound of spectral radius in terms of degree deviation
Wenqian Zhang

Abstract
Let G G be a graph with n n vertices and m m edges. The spectral radius ρ ⁡ ( G ) \rho(G) of G G is the largest eigenvalue of the adjacency matrix of G G . As is well known, ρ ⁡ ( G ) ≥ 2 ​ m n \rho(G)\geq\frac{2m}{n} with equality if and only if G G is regular. To bound ρ ⁡ ( G ) − 2 ​ m n \rho(G)-\frac{2m}{n} , Nikiforov (2006) introduced the degree deviation of G G as s ⁡ ( G ) = ∑ 1 ≤ i ≤ n | d i − 2 ​ m n | , s(G)=\sum_{1\leq i\leq n}|d_{i}-\frac{2m}{n}|, where d 1 , d 2 , … , d n d_{1},d_{2},\ldots,d_{n} are the degrees of the vertices of G G . Nikiforov conjectured that ρ ⁡ ( G ) − 2 ​ m n ≤ 1 2 ​ s ​ ( G ) \rho(G)-\frac{2m}{n}\leq\sqrt{\frac{1}{2}s(G)} for sufficiently large m m and n n . In this paper, we settle this conjecture without the assumption that m m and n n are large. Keywords: spectral radius; degree deviation; irregularity; adjacency matrix. 2020 Mathematics Subject Classification: 05C50.

†
†
footnotetext:
E-mails: [email protected]

1
Introduction

All graphs considered here are finite, undirected and without loops or multiple edges. For a graph
G
, let
V(G)
and
E(G)
denote the vertex set and edge set of
G
, respectively. Let
1,2,...,n
be all the vertices of
G
. The
adjacency matrix

A(G)=(a_{ij})
of
G
is an
n\times n
square matrix indexed by the vertices of
G
, where
a_{ij}=1
if and only if
i
is adjacent to
j
in
G
. The
spectral radius

\rho(G)
of
G
is the largest eigenvalue of
A(G)
. The study of spectral radius of graphs has attracted a large amount of researchers (for example, see
[
1
,
3
,
7
,
8
,
10
,
11
,
13
]
). For any terminology used but not defined here, one may refer to
[
2
,
4
]
.

Let
G
be a graph with
n
vertices and
m
edges. Collatz and Sinogowitz
[
5
]
showed that
\rho(G)\geq\frac{2m}{n}
. Since the
equality holds if and only if
G
is a
\frac{2m}{n}
-regular graph, they proposed the value
\rho(G)-\frac{2m}{n}
as a
relevant measure of irregularity of
G
. To bound
\rho(G)-\frac{2m}{n}
, Nikiforov
[
9
]
introduced the
degree deviation
of
G
as

s(G)=\sum_{u\in V(G)}|d_{i}-\frac{2m}{n}|,

where
d_{1},d_{2},\ldots,d_{n}
are the degrees of the vertices of
G
. For the upper bound of
\rho(G)-\frac{2m}{n}
, Nikiforov
[
9
]
proposed the following conjecture.

Conjecture 1
(Nikiforov
[
9
]
). Let
G
be a graph with
n
vertices and
m
edges. Then
\rho(G)-\frac{2m}{n}\leq\sqrt{\frac{1}{2}s(G)}
for sufficiently large
m
and
n
.

The constant
\frac{1}{2}
in Conjecture 1 is best possible. For example, let
G
be the star graph on
n
vertices. Note that
m=|E(G)|=n-1
and
\rho(G)=\sqrt{n-1}
. It is easy to check that

\frac{\rho(G)-\frac{2m}{n}}{\sqrt{s(G)}}\rightarrow\sqrt{\frac{1}{2}}

when
n\rightarrow\infty
.

For the progress on Conjecture 1, (without the assumption that
n
and
m
are large), Nikiforov
[
9
]
proved that
\rho(G)-\frac{2m}{n}\leq\sqrt{s(G)}
. Zhang
[
14
]
proved that
\rho(G)-\frac{2m}{n}\leq\sqrt{\frac{9}{10}s(G)}
. Very recently, Rautenbach and Werner
[
12
]
showed that
\rho(G)-\frac{2m}{n}\leq\sqrt{\frac{2}{3}s(G)}
. In this paper, we settle Conjecture 1 in a stronger form as follows.

Theorem 1.1

Let
G
be a graph with
n
vertices and
m
edges. Then
\rho(G)-\frac{2m}{n}\leq\sqrt{\frac{1}{2}s(G)}
.

To begin the proof of Theorem
1.1
, we point out for the readers that Rautenbach and Werner obtained their result
[
12
]
before this paper, and the method used there is different from the current one.

2
The Proof of Theorem
1.1

For a matrix
A
, let
r_{i}(A)
be the
i
-th row sum of
A
. The following lemma is deduced from Lemma 2.1 of
[
6
]
.

Lemma 2.1

(Ellingham and Zha
[
6
]
)
Let
G
be a graph with spectral radius
\rho
, and let
A
be its adjacency matrix. For any polynomial
f(x)
, we have

f(\rho)\leq\max_{u\in V(G)}r_{u}(f(A)).

Now we are in the stage to prove the main theorem of this paper.

Proof of Theorem
1.1
.
Let
d=\lceil\frac{2m}{n}\rceil
. For any
u\in V(G)
, let
N(u)
be the set of vertices adjacent to
u
in
G
, and let
d(u)=|N(u)|
. For any integer
k\geq 0
, let
W_{\geq k}
(and
W_{\leq k}
, respectively) be the set of vertices of degree at least
k
(and at most
k
, respectively) in
G
. Let

s=s(G)=\sum_{v\in V(G)}|d(v)-\frac{2m}{n}|.

Since
\sum_{v\in V(G)}(d(v)-\frac{2m}{n})=0
, we have

\sum_{v\in W_{\geq d}}(d(v)-\frac{2m}{n})=\frac{1}{2}s.

Thus

\sum_{v\in W_{\geq d}}(d(v)-d)\leq\sum_{v\in W_{\geq d}}(d(v)-\frac{2m}{n})=\frac{1}{2}s.

Let
A=A(G)
and
\rho=\rho(G)
. We will show that
r_{u}(A^{2}-(d-1)A)\leq d+\frac{1}{2}s
for any
u\in V(G)
in two cases as follows.

Case 1
.
d(u)\leq d-1
.

Note that
u\notin W_{\geq d}
in this case.
Then

\displaystyle r_{u}(A^{2})

\displaystyle=\sum_{v\in N(u)}d(v)

\displaystyle=\left(\sum_{v\in N(u)\cap W_{\leq d-1}}d(v)\right)+\left(\sum_{v\in N(u)\cap W_{\geq d}}d(v)\right)

\displaystyle\leq(d-1)|N(u)\cap W_{\leq d-1}|+\left(\sum_{v\in N(u)\cap W_{\geq d}}(d(v)-d)\right)+d|N(u)\cap W_{\geq d}|

\displaystyle\leq d|N(u)|+\sum_{v\in W_{\geq d}}(d(v)-d)

\displaystyle\leq(d-1)d(u)+d-1+\frac{1}{2}s

\displaystyle<(d-1)d(u)+d+\frac{1}{2}s.

Note that
r_{u}(A)=d(u)
. It follows that
r_{u}(A^{2}-(d-1)A)\leq d+\frac{1}{2}s
.

Case 2
.
d(u)\geq d
.

Note that
u\in W_{\geq d}
in this case.
Then

\displaystyle r_{u}(A^{2})

\displaystyle=\sum_{v\in N(u)}d(v)

\displaystyle=\left(\sum_{v\in N(u)\cap W_{\leq d-1}}d(v)\right)+\left(\sum_{v\in N(u)\cap W_{\geq d}}d(v)\right)

\displaystyle\leq(d-1)|N(u)\cap W_{\leq d-1}|+\left(\sum_{v\in N(u)\cap W_{\geq d}}(d(v)-d)\right)+d|N(u)\cap W_{\geq d}|

\displaystyle\leq d|N(u)|+\sum_{v\in W_{\geq d},v\neq u}(d(v)-d)

\displaystyle=(d-1)d(u)+d(u)+\left(\sum_{v\in W_{\geq d}}(d(v)-d)\right)-(d(u)-d)

\displaystyle=(d-1)d(u)+d+\left(\sum_{v\in W_{\geq d}}(d(v)-d)\right)

\displaystyle\leq(d-1)d(u)+d+\frac{1}{2}s.

It follows that
r_{u}(A^{2}-(d-1)A)\leq d+\frac{1}{2}s
.

Let
f(x)=x^{2}-(d-1)x
. By the discussion of Case 1 and Case 2, we have that
r_{u}(f(A))\leq d+\frac{1}{2}s
for any
u\in V(G)
. By Lemma
2.1
, we have
f(\rho)\leq d+\frac{1}{2}s
. That is
\rho^{2}-(d-1)\rho\leq d+\frac{1}{2}s
. It follows that

\rho\leq\frac{d-1}{2}+\sqrt{\frac{(d+1)^{2}}{4}+\frac{1}{2}s}\leq\frac{d-1}{2}+\left(\sqrt{\frac{(d+1)^{2}}{4}}+\sqrt{\frac{1}{2}s}\right)=d+\sqrt{\frac{1}{2}s}.

Then
\rho-\frac{2m}{n}\leq\rho-d+1\leq 1+\sqrt{\frac{1}{2}s}
.

As above, we have shown that
\rho(G)-\frac{2m}{n}\leq 1+\sqrt{\frac{1}{2}s(G)}
for any graph
G
with
n
vertices and
m
edges.

For any integer
t\geq 1
, as in
[
9
]
, let
G^{(t)}
be the graph obtained from
G
by replacing each vertex
u
in
G
with an independent set
V_{u}
of
t
new vertices, and connecting
x\in V_{u}
to
y\in V_{v}
if and only if
u
is adjacent to
v
in
G
. By Theorem 5 of
[
9
]
, we have
\rho(G^{(t)})=t\rho(G)
. Clearly, the average degree of
G^{(t)}
equals
\frac{2m}{n}t
, and
s(G^{(t)})=t^{2}s(G)
. Applying the result in the last paragraph to
G^{(t)}
, we have
t\rho(G)-\frac{2m}{n}t\leq 1+\sqrt{\frac{1}{2}t^{2}s(G)}
. By letting
t\rightarrow\infty
, we obtain that
\rho(G)-\frac{2m}{n}\leq\sqrt{\frac{1}{2}s(G)}
. This completes the proof.
\Box

Data availability statement

There is no associated data.

Declaration of Interest Statement

Read the complete text