A tree is classified as being type I provided that there are two or more Perron branches at its characteristic vertex. The question arises as to how one might construct such a tree in which the Perron branches at the characteristic vertex are not isomorphic. Motivated by an example of Grone and Merris, we produce a large class of such trees, and show how to construct others from them. We also investigate some of the properties of a subclass of these trees. Throughout, we exploit connections between...

We consider an accessibility index for the states of a discrete-time, ergodic, homogeneous Markov chain on a finite state space; this index is naturally associated with the random walk centrality introduced by Noh and Reiger (2004) for a random walk on a connected graph. We observe that the vector of accessibility indices provides a partition of Kemeny's constant for the Markov chain. We provide three characterizations of this accessibility index: one in terms of the first return time to the state...

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...

Let $A$ be an $n\times n$ symmetric, irreducible, and nonnegative matrix whose eigenvalues are ${\lambda}_{1}>{\lambda}_{2}\ge ...\ge {\lambda}_{n}$. In this paper we derive several lower and upper bounds, in particular on ${\lambda}_{2}$ and ${\lambda}_{n}$, but also, indirectly, on $\mu ={max}_{2\le i\le n}\left|{\lambda}_{i}\right|$. The bounds are in terms of the diagonal entries of the group generalized inverse, ${Q}^{\#}$, of the singular and irreducible M-matrix $Q={\lambda}_{1}I-A$. Our starting point is a spectral resolution for ${Q}^{\#}$. We consider the case of equality in some of these inequalities and we apply our results to the algebraic connectivity of undirected...

Let $G$ be a $k$-connected graph with $k\ge 2$. A hinge is a subset of $k$ vertices whose deletion from $G$ yields a disconnected graph. We consider the algebraic connectivity and Fiedler vectors of such graphs, paying special attention to the signs of the entries in Fiedler vectors corresponding to vertices in a hinge, and to vertices in the connected components at a hinge. The results extend those in Fiedler’s papers Algebraic connectivity of graphs (1973), A property of eigenvectors of nonnegative symmetric...

Download Results (CSV)