Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.16839 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913904169320448 |
|---|---|
| author | Ke, Yingyue Haemers, Willem H. Van Mieghem, Piet |
| author_facet | Ke, Yingyue Haemers, Willem H. Van Mieghem, Piet |
| contents | Threshold graphs are generated from one node by repeatedly adding a node that links to all existing nodes or adding a node without links. In the weighted threshold graph, we add a new node in step $i$, which is linked to all existing nodes by a link of weight $w_i$. In this work, we consider the set ${\cal A}_N$ that contains all Laplacian matrices of weighted threshold graphs of order $N$. We show that ${\cal A}_N$ forms a commutative algebra. Using this, we find a common basis of eigenvectors for the matrices in ${\cal A}_N$. It follows that the eigenvalues of each matrix in ${\cal A}_N$ can be represented as a linear transformation of the link weights. In addition, we prove that, if there are just three or fewer different weights, two weighted threshold graphs with the same Laplacian spectrum must be isomorphic. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_16839 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Laplacian matrix of weighted threshold graphs Ke, Yingyue Haemers, Willem H. Van Mieghem, Piet Combinatorics Commutative Algebra Threshold graphs are generated from one node by repeatedly adding a node that links to all existing nodes or adding a node without links. In the weighted threshold graph, we add a new node in step $i$, which is linked to all existing nodes by a link of weight $w_i$. In this work, we consider the set ${\cal A}_N$ that contains all Laplacian matrices of weighted threshold graphs of order $N$. We show that ${\cal A}_N$ forms a commutative algebra. Using this, we find a common basis of eigenvectors for the matrices in ${\cal A}_N$. It follows that the eigenvalues of each matrix in ${\cal A}_N$ can be represented as a linear transformation of the link weights. In addition, we prove that, if there are just three or fewer different weights, two weighted threshold graphs with the same Laplacian spectrum must be isomorphic. |
| title | The Laplacian matrix of weighted threshold graphs |
| topic | Combinatorics Commutative Algebra |
| url | https://arxiv.org/abs/2506.16839 |