Measure-theoretic bounds on the spectral radius of graphs from walks
Measure-theoretic bounds on the spectral radius of graphs from walks
复制标题
步行图谱半径的测量理论界限
DOI：
10.1016/j.laa.2021.04.023
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Preciado, Victor M.
中科院分区：
文献类型：
--
作者：
Barreras, Francisco;Hayhoe, Mikhail;Hassani, Hamed;Preciado, Victor M.
设G是一个无向图，它的邻接矩阵为A，谱半径为ρ。设w k， φ k和φ k (i)分别为k步后长度为k的行走次数，长度为k的封闭行走次数，以及从顶点i开始和结束的封闭行走次数。在本文中，我们提出了一个测量理论框架，使我们能够将图中的行走与其谱性质联系起来。特别是，我们表明，w k， ϕ k和ϕ k (i)可以被解释为三个不同测度的矩，所有这些都支持在a的频谱上。在这种解释的基础上，我们利用经典矩问题的结果来制定ρ的新下界和上界的层次结构，并为文献中几个知名的界提供替代证明。
Let G be an undirected graph with adjacency matrix A and spectral radius ρ. Let w k, ϕ k and ϕ k (i) be, respectively, the number walks of length k, closed walks of length k and closed walks starting and ending at vertex i after k steps. In this paper, we propose a measure-theoretic framework which allows us to relate walks in a graph with its spectral properties. In particular, we show that w k, ϕ k and ϕ k (i) can be interpreted as the moments of three different measures, all of them supported on the spectrum of A. Building on this interpretation, we leverage results from the classical moment problem to formulate a hierarchy of new lower and upper bounds on ρ, as well as provide alternative proofs to several well-known bounds in the literature.
DOI：
--
发表时间：
2019-08
期刊：
arXiv: Rings and Algebras
影响因子：
--
作者：
Peter B. Denton;Stephen J. Parke;Terence Tao;Xining Zhang
通讯作者：
Peter B. Denton;Stephen J. Parke;Terence Tao;Xining Zhang
评估“均匀填充”决定因素
DOI：
--
发表时间：
1988
期刊：
影响因子：
--
作者：
S. M. Goberstein
通讯作者：
S. M. Goberstein