# Partially ordering weighted trees using discrete Green's functions

@inproceedings{Zeng2021PartiallyOW, title={Partially ordering weighted trees using discrete Green's functions}, author={Ji Zeng}, year={2021} }

In this paper, we consider the edge transfer operation for which we remove an edge incident to a vertex and connect one of its neighbors to the other endpoint of this removed edge. We show that if an edge of a weighted tree is transferred from a vertex to another vertex with smaller diagonal value on the combinatorial Green’s function, the resulting tree has smaller Kemeny’s constant. Consequently, this leads to a partial order on the family of trees. Maximal and minimal elements of this… Expand

#### References

SHOWING 1-10 OF 16 REFERENCES

Forest formulas of discrete Green's functions

- Mathematics
- 2021

Abstract. The discrete Green’s functions are the pseudoinverse (or the inverse) of the Laplacian (or its variations) of a graph. In this paper, we will give combinatorial interpretations of Green’s… Expand

Partially ordering the class of invertible trees

- Mathematics, Computer Science
- Eur. J. Comb.
- 2020

A new proof of this theorem is given, which gives rise to a partial ordering relation on the class of all invertible trees on 2n vertices, that given an invertable tree T whose inverse graph has strictly more edges, it can remove an edge from T and add another edge to obtain an inverted tree T' whose median eigenvalue is strictly greater. Expand

A Combinatorial Laplacian with Vertex Weights

- Computer Science, Mathematics
- J. Comb. Theory, Ser. A
- 1996

The matrix-tree theorem is generalized to matrix-Tree theorems of counting “rooted” directed spanning trees and the characteristic polynomial of the vertex-weighted Laplacian has coefficients with similar interpretations. Expand

On Kemeny's constant for trees with fixed order and diameter

- Mathematics
- 2020

Kemeny's constant $\kappa(G)$ of a connected graph $G$ is a measure of the expected transit time for the random walk associated with $G$. In the current work, we consider the case when $G$ is a tree,… Expand

The characteristic polynomial of a graph

- Mathematics
- 1972

Abstract The present paper is addressed to the problem of determining under what conditions the characteristic polynomial of the adjacency matrix of a graph distinguishes between non-isomorphic… Expand

A partially ordered set of functionals corresponding to graphs

- Mathematics, Computer Science
- Discret. Math.
- 1994

It is proved that the number of homomorphisms into every graph H from G is not less than from L, and the first and the second maximal elements of this poset of k-edge trees are found. Expand

Inverses of trees

- Mathematics, Computer Science
- Comb.
- 1985

It is shown that in fact A−1 is diagonally similar to a (0, 1)-matrix, hence to the adjacency matrix of a graph, Hence sharp bounds on the least positive eigenvalue of A are provided. Expand

PageRank and Random Walks on Graphs

- Computer Science
- 2010

It is illustrated that the generalized hitting time leads to finding sparse cuts and efficient approximation algorithms for PageRank can be used for approximating hitting time and effective resistance. Expand

Forest Matrices Around the Laplaeian Matrix

- Mathematics, Chemistry
- 2002

Abstract We study the matrices Q k of in-forests of a weighted digraph Γ and their connections with the Laplacian matrix L of Γ . The ( i , j ) entry of Q k is the total weight of spanning converging… Expand

The Kemeny Constant for Finite Homogeneous Ergodic Markov Chains

- Mathematics, Computer Science
- J. Sci. Comput.
- 2010

A new formula for the Kemeny constant is presented and several perturbation results for the constant are developed, including conditions under which it is a convex function and for chains whose transition matrix has a certain directed graph structure. Expand