Eccentricity and algebraic connectivity of graphs
Eccentricity and algebraic connectivity of graphs
Let $G$ be a graph on $n$ nodes with algebraic connectivity $λ_{2}$. The eccentricity of a node is defined as the length of a longest shortest path starting at that node. If $s_\ell$ denotes the number of nodes of eccentricity at most $\ell$, then for $\ell \ge 2$, $$λ_{2} \ge \frac{ 4 \, s_\ell }{ (\ell-2+\frac{4}{n}) \, n^2 }.$$ As a corollary, if $d$ denotes the diameter of $G$, then $$λ_{2} \ge \frac{ 4 }{ (d-2+\frac{4}{n}) \, n }.$$ It is also shown that $$λ_{2} \ge \frac{ s_\ell }{ 1+ \ell \left(e(G^{\ell})-m\right) },$$ where $m$ and $e(G^\ell)$ denote the number of edges in $G$ and in the $\ell$-th power of $ G $, respectively.
B. Afshari、M. Afshari
数学
B. Afshari,M. Afshari.Eccentricity and algebraic connectivity of graphs[EB/OL].(2025-06-30)[2025-07-25].https://arxiv.org/abs/2407.02535.点此复制
评论