论文标题
最小代数连通性和最大直径：aldous-填充和Guiduli-Mohar猜想
Minimum algebraic connectivity and maximum diameter: Aldous--Fill and Guiduli--Mohar conjectures
论文作者
论文摘要
Aldous and Fill（2002）指出，在带有$ n $ Vertices的连接的常规图上随机步行的最大放松时间为$（1+O（1））\ frac {3n^{2}} {2π^{2}}} $。 Guiduli和Mohar（1996）的猜想预测了该图的结构，其代数连接$μ$是所有最低度$δ$的连接图中最小的图。我们证明了这个猜想意味着千美元$ d $的猜想。我们对最低$ $ $的$ d $规范图的结构提出了另一个猜想，这也表明这也意味着Aldous-填写猜测，甚至构成$ d $。在文献中，从经验上注意到，小$ $ $的图形往往具有较大的直径。在这方面，Guiduli（1996）询问直径最大的立方图是否具有比其他所有方格的代数连接性。由这些动机，我们研究了最大直径的图与具有最小代数连通性的图形之间的相互作用。我们表明，Guiduli问题的答案是其一般形式的答案，即每$ d \ ge 3 $的$ d $等级图是负的。我们旨在开发问题的渐近公式。事实证明，$ d $的$ d \ ge 5 $以及$δ= d $的图形$ d $ for $ d \ ge 4 $，渐近最大直径，不一定表现出渐近性最小的$ $ $ $。我们猜想具有渐近最小$μ$的$ D $ regratular图（或具有$δ= D $的图形）应具有渐近最大直径。以上结果很大程度上取决于我们对结构的理解以及对几乎最大直径图的代数连接性的最佳估计，从中，该图的aldous-填写了该图。
Aldous and Fill (2002) conjectured that the maximum relaxation time for the random walk on a connected regular graph with $n$ vertices is $(1+o(1)) \frac{3n^{2}}{2π^{2}}$. A conjecture by Guiduli and Mohar (1996) predicts the structure of graphs whose algebraic connectivity $μ$ is the smallest among all connected graphs whose minimum degree $δ$ is a given $d$. We prove that this conjecture implies the Aldous--Fill conjecture for odd $d$. We pose another conjecture on the structure of $d$-regular graphs with minimum $μ$, and show that this also implies the Aldous--Fill conjecture for even $d$. In the literature, it has been noted empirically that graphs with small $μ$ tend to have a large diameter. In this regard, Guiduli (1996) asked if the cubic graphs with maximum diameter have algebraic connectivity smaller than all others. Motivated by these, we investigate the interplay between the graphs with maximum diameter and those with minimum algebraic connectivity. We show that the answer to Guiduli problem in its general form, that is for $d$-regular graphs for every $d\ge 3$ is negative. We aim to develop an asymptotic formulation of the problem. It is proven that $d$-regular graphs for $d\ge 5$ as well as graphs with $δ=d$ for $d\ge 4$ with asymptotically maximum diameter, do not necessarily exhibit the asymptotically smallest $μ$. We conjecture that $d$-regular graphs (or graphs with $δ=d$) that have asymptotically smallest $μ$, should have asymptotically maximum diameter. The above results rely heavily on our understanding of the structure as well as optimal estimation of the algebraic connectivity of nearly maximum-diameter graphs, from which the Aldous--Fill conjecture for this family of graphs also follows.
