Эта публикация цитируется в
6 статьях
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
Аннотация:
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.
Ключевые слова:
tree, eigenvalues of graphs, spectral radius of graphs, maximum degree.
MSC: 05C31,
05C50,
15A18 Поступила в редакцию: 27.09.2016
Исправленный вариант: 09.11.2016
Язык публикации: английский