|
Algebra and Discrete Mathematics, 2017, Volume 24, Issue 2, Pages 302–307
(Mi adm635)
|
|
|
|
This article is cited in 6 scientific papers (total in 6 papers)
RESEARCH ARTICLE
On the difference between the spectral radius and the maximum degree of graphs
Mohammad Reza Oboudiab a Department of Mathematics, College of Sciences, Shiraz University, Shiraz, 71457-44776, Iran
b School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box: 19395-5746, Tehran, Iran
Abstract:
Let $G$ be a graph with the eigenvalues $\lambda_1(G)\geq\cdots\geq\lambda_n(G)$. The largest eigenvalue of $G$, $\lambda_1(G)$, is called the spectral radius of $G$. Let $\beta(G)=\Delta(G)-\lambda_1(G)$, where $\Delta(G)$ is the maximum degree of vertices of $G$. It is known that if $G$ is a connected graph, then $\beta(G)\geq0$ and the equality holds if and only if $G$ is regular. In this paper we study the maximum value and the minimum value of $\beta(G)$ among all non-regular connected graphs. In particular we show that for every tree $T$ with $n\geq3$ vertices, $n-1-\sqrt{n-1}\geq\beta(T)\geq 4\sin^2(\frac{\pi}{2n+2})$. Moreover, we prove that in the right side the equality holds if and only if $T\cong P_n$ and in the other side the equality holds if and only if $T\cong S_n$, where $P_n$ and $S_n$ are the path and the star on $n$ vertices, respectively.
Keywords:
tree, eigenvalues of graphs, spectral radius of graphs, maximum degree.
Received: 27.09.2016 Revised: 09.11.2016
Citation:
Mohammad Reza Oboudi, “On the difference between the spectral radius and the maximum degree of graphs”, Algebra Discrete Math., 24:2 (2017), 302–307
Linking options:
https://www.mathnet.ru/eng/adm635 https://www.mathnet.ru/eng/adm/v24/i2/p302
|
Statistics & downloads: |
Abstract page: | 233 | Full-text PDF : | 107 | References: | 32 |
|