On the difference between the spectral radius and the maximum degree of graphs
Let G be a graph with the eigenvalues λ₁(G)≥⋯≥λn(G). The largest eigenvalue of G, λ₁(G), is called the spectral radius of G. Let β(G)=Δ(G)−λ₁(G), where Δ(G) is the maximum degree of vertices of G. It is known that if G is a connected graph, then β(G)≥0 and the equality holds if and only if G is regu...
Gespeichert in:
| Veröffentlicht in: | Algebra and Discrete Mathematics |
|---|---|
| Datum: | 2017 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2017
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/156636 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | On the difference between the spectral radius and the maximum degree of graphs / M.R. Oboudi // Algebra and Discrete Mathematics. — 2017. — Vol. 24, № 2. — С. 302-307. — Бібліогр.: 17 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-156636 |
|---|---|
| record_format |
dspace |
| spelling |
Oboudi, M.R. 2019-06-18T18:15:53Z 2019-06-18T18:15:53Z 2017 On the difference between the spectral radius and the maximum degree of graphs / M.R. Oboudi // Algebra and Discrete Mathematics. — 2017. — Vol. 24, № 2. — С. 302-307. — Бібліогр.: 17 назв. — англ. 1726-3255 2010 MSC:05C31, 05C50, 15A18. https://nasplib.isofts.kiev.ua/handle/123456789/156636 Let G be a graph with the eigenvalues λ₁(G)≥⋯≥λn(G). The largest eigenvalue of G, λ₁(G), is called the spectral radius of G. Let β(G)=Δ(G)−λ₁(G), where Δ(G) is the maximum degree of vertices of G. It is known that if G is a connected graph, then β(G)≥0 and the equality holds if and only if G is regular. In this paper we study the maximum value and the minimum value of β(G) among all non-regular connected graphs. In particular we show that for every tree T with n≥3 vertices, n−1−√(n−1) ≥ β(T) ≥ 4sin²(π/(2n+2)). Moreover, we prove that in the right side the equality holds if and only if T≅Pn and in the other side the equality holds if and only if T≅Sn, where Pn and Sn are the path and the star on n vertices, respectively. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics On the difference between the spectral radius and the maximum degree of graphs Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
On the difference between the spectral radius and the maximum degree of graphs |
| spellingShingle |
On the difference between the spectral radius and the maximum degree of graphs Oboudi, M.R. |
| title_short |
On the difference between the spectral radius and the maximum degree of graphs |
| title_full |
On the difference between the spectral radius and the maximum degree of graphs |
| title_fullStr |
On the difference between the spectral radius and the maximum degree of graphs |
| title_full_unstemmed |
On the difference between the spectral radius and the maximum degree of graphs |
| title_sort |
on the difference between the spectral radius and the maximum degree of graphs |
| author |
Oboudi, M.R. |
| author_facet |
Oboudi, M.R. |
| publishDate |
2017 |
| language |
English |
| container_title |
Algebra and Discrete Mathematics |
| publisher |
Інститут прикладної математики і механіки НАН України |
| format |
Article |
| description |
Let G be a graph with the eigenvalues λ₁(G)≥⋯≥λn(G). The largest eigenvalue of G, λ₁(G), is called the spectral radius of G. Let β(G)=Δ(G)−λ₁(G), where Δ(G) is the maximum degree of vertices of G. It is known that if G is a connected graph, then β(G)≥0 and the equality holds if and only if G is regular. In this paper we study the maximum value and the minimum value of β(G) among all non-regular connected graphs. In particular we show that for every tree T with n≥3 vertices, n−1−√(n−1) ≥ β(T) ≥ 4sin²(π/(2n+2)). Moreover, we prove that in the right side the equality holds if and only if T≅Pn and in the other side the equality holds if and only if T≅Sn, where Pn and Sn are the path and the star on n vertices, respectively.
|
| issn |
1726-3255 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/156636 |
| citation_txt |
On the difference between the spectral radius and the maximum degree of graphs / M.R. Oboudi // Algebra and Discrete Mathematics. — 2017. — Vol. 24, № 2. — С. 302-307. — Бібліогр.: 17 назв. — англ. |
| work_keys_str_mv |
AT oboudimr onthedifferencebetweenthespectralradiusandthemaximumdegreeofgraphs |
| first_indexed |
2025-11-24T06:35:37Z |
| last_indexed |
2025-11-24T06:35:37Z |
| _version_ |
1850843123986464768 |
| fulltext |
“adm-n4” 18:32 page #124
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 24 (2017). Number 2, pp. 302–307
© Journal “Algebra and Discrete Mathematics”
On the difference between the spectral radius
and the maximum degree of graphs∗
Mohammad Reza Oboudi
Communicated by V. Mazorchuk
Abstract. Let G be a graph with the eigenvalues λ1(G) >
· · · > λn(G). The largest eigenvalue of G, λ1(G), is called the
spectral radius of G. Let β(G) = ∆(G) − λ1(G), where ∆(G) is
the maximum degree of vertices of G. It is known that if G is a
connected graph, then β(G) > 0 and the equality holds if and only
if G is regular. In this paper we study the maximum value and the
minimum value of β(G) among all non-regular connected graphs.
In particular we show that for every tree T with n > 3 vertices,
n − 1 −
√
n − 1 > β(T ) > 4 sin2( π
2n+2
). Moreover, we prove that in
the right side the equality holds if and only if T ∼= Pn and in the
other side the equality holds if and only if T ∼= Sn, where Pn and
Sn are the path and the star on n vertices, respectively.
1. Introduction
Throughout this paper all graphs are simple, that is finite and undi-
rected without loops and multiple edges. Let G = (V, E) be a simple
graph. The order of G denotes the number of vertices of G. For two
vertices u and v by e = uv we mean the edge e between u and v. For two
graphs G1 = (V1, E1) and G2 = (V2, E2), the disjoint union of G1 and
G2 denoted by G1 + G2 is the graph with vertex set V1 ∪ V2 and edge set
∗This research was in part supported by a grant from IPM (No. 95050012).
2010 MSC: 05C31, 05C50, 15A18.
Key words and phrases: tree, eigenvalues of graphs, spectral radius of graphs,
maximum degree.
“adm-n4” 18:32 page #125
M. R. Oboudi 303
E1 ∪ E2. The graph rG denotes the disjoint union of r copies of G. For
every vertex v ∈ V (G), the degree of v is the number of edges incident
with v and is denoted by degG(v). A regular graph is a graph that all
of its vertices have the same degree. By ∆(G) we mean the maximum
degree of vertices of G. For two vertices u and v of connected graph G, the
distance between u and v in G that is denoted by d(u, v), is the length of
a shortest path between u and v. The greatest distance between any two
vertices of G is the diameter of G, denoted by diam(G). The complete
graph, the cycle, and the path of order n, are denoted by Kn, Cn and Pn,
respectively. We denote the complete bipartite graph with part sizes m
and n, by Km,n. The star of order n that is denoted by Sn is the complete
bipartite graph K1,n−1.
Let G be a graph with vertex set {v1, . . . , vn}. The adjacency matrix
of G, A(G) = [aij ], is an n × n matrix such that aij = 1 if vi and vj are
adjacent, and otherwise aij = 0. Thus A(G) is a symmetric matrix with
zeros on the diagonal and all the eigenvalues of A(G) are real. By the
eigenvalues of G we mean those of its adjacency matrix. We denote the
eigenvalues of G by λ1(G) > · · · > λn(G). By the spectral radius of G we
mean λ1(G). We note that λ1(G) is also called the index of G. It is well
known that |λi(G)| 6 λ1(G), for i = 1, . . . , n. Many papers are devoted to
study the characteristic polynomials and spectra of the adjacency matrix
of graphs, in particular characterization of graphs by their eigenvalues
and finding the location of eigenvalues of graphs, see [1]–[17] and the
references therein. Studying the spectral radius of graphs has always been
of great interest to researchers in graph theory, for instance see [1], [3], [5],
[6], [11] and [13]–[17].
Let G be a graph. It is a well known fact that λ1(G) 6 ∆(G). Moreover
if G is connected, then the equality holds if and only if G is regular.
Therefore it is natural to ask about the value of ∆(G) − λ1(G). For
a graph G by β(G) we mean β(G) = ∆(G) − λ1(G). Hence for every
graph G, β(G) > 0. Also if G is connected, then G is regular if and
only if β(G) = 0. One can regard β(G) as a parameter that indicates
the measure of irregularity of G. There are some papers related this
parameter. Cioabă [3] has proved that if G is a non-regular connected
graph of order n, then ∆(G) − λ1(G) > 1
nd
, where d = diam(G). In this
paper we study the maximum value and the minimum value of β(G)
among all non-regular graphs. We show among all non-regular graphs
the stars have the maximum value of β. We prove that for every tree T
with n > 3 vertices, n − 1 −
√
n − 1 > β(T ) > 4 sin2( π
2n+2
). Moreover
we obtain that in the right side the equality holds if and only if T ∼= Pn
“adm-n4” 18:32 page #126
304 On the difference between the spectral radius. . .
and in the other side the equality holds if and only if T ∼= Sn. Finally we
conjecture that among all non-regular connected graph the paths have
the minimum value of β.
2. Results
In this section we obtain the maximum and the minimum value of
the difference between the spectral radius and the maximum degree of
non-regular connected graphs. We need the following result.
Theorem 1. [4] Let G be a connected graph. If H is a proper subgraph
of G, then λ1(G) > λ1(H).
Now we show that among all graphs the stars attain the maximum
value of β.
Theorem 2. Let G be a graph of order n. Then
β(G) 6 β(Sn) = n − 1 −
√
n − 1.
Moreover the equality holds if and only if G ∼= Sn.
Proof. First we prove the theorem for connected graphs. Let H be a
connected graph of order t. Suppose that H ≇ St. We show that β(H) <
β(St). For t = 1, there is noting to prove. So let t > 2. Let h = ∆(H).
Hence h > 1. Since Sh+1 is a proper subgraph of H, by Theorem 1 we
obtain that
λ1(H) > λ1(Sh+1) =
√
h. (1)
For every x > 0, let f(x) = x − √
x. This function is increasing on the
interval [1
4
, ∞). Since t − 1 > h > 1 by (1),
β(St) = t−1−
√
t − 1 = f(t−1) > f(h) = h−
√
h > h −λ1(H) = β(H).
So for connected graphs the result follows. Now assume that G ≇ Sn be
a non-connected graph of order n. So ∆(G) 6 n − 2. If ∆(G) = 0, there
is nothing to prove. Hence 1 6 ∆(G) 6 n − 2. On the other hand similar
to above, one can see that λ1(G) >
√
∆(G). Since n − 1 > ∆(G) > 1,
f(n − 1) > f(∆(G)) = ∆(G) −
√
∆(G) > ∆(G) − λ1(G) = β(G).
Therefore β(G) < f(n − 1) = n − 1 −
√
n − 1. The proof is complete.
“adm-n4” 18:32 page #127
M. R. Oboudi 305
Remark 1. For every n > 2, let Hn = Kn+K1. Then ∆(Hn) = λ1(Hn) =
n − 1. Therefore β(Hn) = 0 while Hn is not regular. This example shows
that the minimum value of β(G) among all non-regular graphs G or order
n > 2 is zero.
In sequel we study the minim value of β(G) among the family of
non-regular connected graphs G. We need the following nice upper bound
on the spectral radius of trees.
Theorem 3. [14] Let T be a tree with maximum degree ∆. Then
λ1(T ) < 2
√
∆ − 1.
Theorem 4. Let T be a tree of order n > 3. Then
β(T ) > β(Pn) = 4 sin2
(
π
2n + 2
)
.
Moreover the equality holds if and only if T ∼= Pn.
Proof. Let n > 3. Since λ1(Pn) = 2 cos π
n+1
and ∆(Pn) = 2, β(Pn) =
2 − 2 cos π
n+1
= 4 sin2( π
2n+2
). For every x > 1, let f(x) = x − 2
√
x − 1.
It is easy to see that f is an increasing function on the interval [2, ∞).
Therefore for every x > 3, f(x) > 3 − 2
√
2. On the other hand it is not
hard to see that for every n > 7, 3 − 2
√
2 > 4 sin2( π
2n+2
). Hence for every
x > 3 and n > 7 we obtain that
f(x) > 4 sin2
(
π
2n + 2
)
. (2)
One can check the result for n 6 6. Now let n > 7. Let T ≇ Pn be a
tree of order n. We show that β(T ) > β(Pn). Since T ≇ Pn, ∆(T ) > 3.
On the other hand by Theorem 3, λ1(T ) < 2
√
∆(T ) − 1. Since ∆(T ) > 3
and n > 7, by (2),
β(T ) = ∆(T ) − λ1(T ) > ∆(T ) − 2
√
∆(T ) − 1
= f(∆(T )) > 4 sin2
(
π
2n + 2
)
= β(Pn).
This completes the proof.
Using Theorems 2 and 4 we obtain the following result.
“adm-n4” 18:32 page #128
306 On the difference between the spectral radius. . .
Theorem 5. Let T be a tree of order n. Then
β(Pn) 6 β(T ) 6 β(Sn).
Moreover in the left side the equality holds if and only if T ∼= Pn and in
the other side the equality holds if and only if T ∼= Sn.
We think that among all non-regular connected graphs G of order n
the path Pn has the minimum value of β. Hence we pose the following
conjecture.
Conjecture 1. Let G be a non-regular connected graph of order n. If
G ≇ Pn, then β(G) > β(Pn).
Now we show that the Conjecture 1 is valid for graphs with small
diameter.
Theorem 6. [3] Let G be a non-regular connected graph of order n. Then
∆(G) − λ1(G) >
1
nd
,
where d is the diameter of G.
Theorem 7. Let G be a non-regular connected graph of order n > 3. If
d = diam(G) 6 n
10
, then β(G) > β(Pn).
Proof. Since 10 > π2, for every n > 1, 10
π2 > ( n
n+1
)2. On the other hand
for n > 1, π
2n+2
> sin( π
2n+2
). Hence for every n > 1, 10
n2 > 4( π
2n+2
)2 >
4 sin2( π
2n+2
). This shows that 1
nd
>
10
n2 > 4 sin2( π
2n+2
). Therefore for every
n > 3, by Theorem 6 we obtain that
∆(G) − λ1(G) >
1
nd
> 4 sin2
(
π
2n + 2
)
= β(Pn).
The proof is complete.
Remark 2. One can see that for every n > 2, λ1(Kn\e) = n−3+
√
n2+2n−7
2
where e is an edge of Kn, see [8]. Therefore limn→∞(β(Kn \ e)) = 0.
References
[1] R.A. Brualdi, A.J. HoIman, On the spectral radius of a (0, 1) matrix, Linear
Algebra and its Applications, 65 (1985) 133–146.
[2] D. Cao, Y. Hong, The distribution of eigenvalues of graphs, Linear Algebra and
its Applications, 216 (1995) 211–224.
“adm-n4” 18:32 page #129
M. R. Oboudi 307
[3] S.M. Cioabă, The spectral radius and the maximum degree of irregular graphs,
The Electronic Journal of Combinatorics 14 (2007), #R38.
[4] D.Cvetković, P. Rowlinson, S. Simić, An introduction to the theory of graph
spectra, London Mathematical Society Student Texts, 75, Cambridge University
Press, Cambridge, 2010.
[5] K.Ch. Das, P. Kumar, Some new bounds on the spectral radius of graphs,
Discrete Mathematics 281 (2004) 149–161.
[6] G.J. Ming, T.Sh.Wang, On the spectral radius of trees, Linear Algebra and its
Applications 329 (2001) 1–8.
[7] M.R. Oboudi, Bipartite graphs with at most six non-zero eigenvalues, Ars
Mathematica Contemporanea 11 (2016) 315–325.
[8] M.R. Oboudi, Characterization of graphs with exactly two non-negative eigen-
values, Ars Mathematica Contemporanea 12 (2017) 271–286.
[9] M.R. Oboudi, Cospectrality of complete bipartite graphs, Linear and Multilinear
Algebra 64 (2016) 2491–2497.
[10] M.R. Oboudi, Energy and Seidel energy of graphs, MATCH Communications in
Mathematical and in Computer Chemistry 75 (2016) 291–303.
[11] M.R. Oboudi, On the eigenvalues and spectral radius of starlike trees, Aequationes
Mathematicae. DOI: 10.1007/s00010-017-0533-4.
[12] M.R. Oboudi, On the third largest eigenvalue of graphs, Linear Algebra and its
Applications 503 (2016) 164–179.
[13] L. Shi, Bounds on the (Laplacian) spectral radius of graphs, Linear Algebra and
its Applications 422 (2007) 755–770.
[14] D. Stevanović, Bounding the largest eigenvalue of trees in terms of the largest
vertex degree, Linear Algebra and its Applications 360 (2003) 35–42.
[15] D. Stevanović, I. Gutman, M.U. Rehman, On spectral radius and energy of
complete multipartite graphs, Ars Mathematica Contemporanea 9 (2015) 109–
113.
[16] B. Wu, E. Xiao,Y. Hong, The spectral radius of trees on k pendant vertices,
Linear Algebra and its Applications 395 (2005) 343–349.
[17] A. Yu, M.Lu, F. Tian, On the spectral radius of graphs, Linear Algebra and its
Applications 387 (2004) 41–49.
Contact information
M. R. Oboudi Department of Mathematics, College of Sciences,
Shiraz University, Shiraz, 71457-44776, Iran;
School of Mathematics, Institute for Research in
Fundamental Sciences (IPM), P.O. Box: 19395-
5746, Tehran, Iran
E-Mail(s): mr_oboudi@yahoo.com,
mr_oboudi@shirazu.ac.ir
Received by the editors: 27.09.2016
and in final form 09.11.2016.
|