On a bound on algebraic connectivity: the case of equality

Title:

On a bound on algebraic connectivity: the case of equality

Creator:

Kirkland, Stephen J. and Neumann, Michael

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:5cabc0f3-84b0-4c5e-962d-064165e46ad2
uuid:5cabc0f3-84b0-4c5e-962d-064165e46ad2

Subject:

math, bounds, eigenvalues, and graphs

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

In a recent paper the authors proposed a lower bound on $1 - \lambda _i$, where $\lambda _i$, $ \lambda _i \ne 1$, is an eigenvalue of a transition matrix $T$ of an ergodic Markov chain. The bound, which involved the group inverse of $I - T$, was derived from a more general bound, due to Bauer, Deutsch, and Stoer, on the eigenvalues of a stochastic matrix other than its constant row sum. Here we adapt the bound to give a lower bound on the algebraic connectivity of an undirected graph, but principally consider the case of equality in the bound when the graph is a weighted tree. It is shown that the bound is sharp only for certain Type I trees. Our proof involves characterizing the case of equality in an upper estimate for certain inner products due to A. Paz.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

65-74

Source:

Czechoslovak Mathematical Journal | 1998 Volume:48 | Number:1

Harvested from:

CDK

Metadata only:

false