Doubly Stochastic Matrices and Modified Laplacian Matrices of Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916964056694784 |
|---|---|
| author | Andrade, Enide Dahl, Geir |
| author_facet | Andrade, Enide Dahl, Geir |
| contents | We consider modified Laplacian matrices of graphs, obtained by adding the identity matrix to the Laplacian matrix $L_G$ of a graph $G$. This results in a positive definite matrix $\tilde{L}_G$. The inverse of $\tilde{L}_G$ is a doubly stochastic matrix. The goal of this paper is to investigate this inverse matrix and how it depends on properties of the underlying graph $G$. In particular, we introduce a general monotonicity property for the entries of the inverse, and derive a sharper version for the case of path graphs. Finally, we show that, in the case of a path graph, the entries of the inverse can be expressed in terms of Fibonacci numbers via an $LU$ factorization. We also establish a lower bound for the diagonal entries of this inverse for a tree as a function of the distances between vertices. Furthermore, we present a simple and efficient algorithm for computing the inverse when the graph is a tree. Moreover, for a general graph, we show that the diagonal entries of this inverse is strictly largest in each row and column. Finally, we discuss a connection to partial differential equations, such as the heat equation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_18773 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Doubly Stochastic Matrices and Modified Laplacian Matrices of Graphs Andrade, Enide Dahl, Geir Combinatorics 05C05, 05C50, 15A18, 15B51 We consider modified Laplacian matrices of graphs, obtained by adding the identity matrix to the Laplacian matrix $L_G$ of a graph $G$. This results in a positive definite matrix $\tilde{L}_G$. The inverse of $\tilde{L}_G$ is a doubly stochastic matrix. The goal of this paper is to investigate this inverse matrix and how it depends on properties of the underlying graph $G$. In particular, we introduce a general monotonicity property for the entries of the inverse, and derive a sharper version for the case of path graphs. Finally, we show that, in the case of a path graph, the entries of the inverse can be expressed in terms of Fibonacci numbers via an $LU$ factorization. We also establish a lower bound for the diagonal entries of this inverse for a tree as a function of the distances between vertices. Furthermore, we present a simple and efficient algorithm for computing the inverse when the graph is a tree. Moreover, for a general graph, we show that the diagonal entries of this inverse is strictly largest in each row and column. Finally, we discuss a connection to partial differential equations, such as the heat equation. |
| title | Doubly Stochastic Matrices and Modified Laplacian Matrices of Graphs |
| topic | Combinatorics 05C05, 05C50, 15A18, 15B51 |
| url | https://arxiv.org/abs/2509.18773 |