论文标题
在归一化的拉普拉斯式的边缘衍生物上，应用于凯门尼的常数
On the Edge Derivative of the Normalized Laplacian with Applications to Kemeny's Constant
论文作者
论文摘要
在连接的图中，Kemeny的常数从任意顶点$ x $中随机步行的预期时间，以达到随机选择的顶点$ y $。因此，凯门尼的常数可以解释为衡量图形如何连接的量度。通常未知边缘如何影响凯门尼的常数。受到归一化拉普拉斯式的定向导数的启发，我们得出了凯门尼常数的定向衍生物，用于几个图家族。此外，我们发现了标准化拉普拉斯的特征值的定向衍生物的尖锐边界和凯门尼常数的定向衍生物边界。
In a connected graph, Kemeny's constant gives the expected time of a random walk from an arbitrary vertex $x$ to reach a randomly-chosen vertex $y$. Because of this, Kemeny's constant can be interpreted as a measure of how well a graph is connected. It is generally unknown how the addition or removal of edges affects Kemeny's constant. Inspired by the directional derivative of the normalized Laplacian, we derive the directional derivative of Kemeny's constant for several graph families. In addition, we find sharp bounds for the directional derivative of an eigenvalue of the normalized Laplacian and bounds for the directional derivative of Kemeny's constant.
