Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.13939 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911542053699584 |
|---|---|
| author | Csikvári, Péter Harangi, Viktor |
| author_facet | Csikvári, Péter Harangi, Viktor |
| contents | Given a connected graph, the principal eigenvector of the adjacency matrix (often called the Perron vector) can be used to assign positive weights to the vertices. A natural way to measure the homogeneousness of this vector is by considering the ratio of its $\ell^1$ and $\ell^2$ norms.
It is easy to see that the most balanced graphs in this sense (i.e., the ones with the largest ratio) are the regular graphs. What can we say about the least balanced (or most centralized) graphs with the smallest ratio? It was conjectured by Rücker, Rücker and Gutman that, for any given $n \geq 6$, among $n$-vertex connected graphs the smallest ratio is achieved by the complete graph $K_4$ with a single path $P_{n-4}$ attached to one of its vertices. In this paper we confirm this conjecture.
We also verify the analogous conjecture for trees: for any given $n \geq 8$, among $n$-vertex trees the smallest ratio is achieved by the star graph $S_5$ with a path $P_{n-5}$ attached to its central vertex. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_13939 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The least balanced graphs and trees Csikvári, Péter Harangi, Viktor Combinatorics 05C50, 15A18 Given a connected graph, the principal eigenvector of the adjacency matrix (often called the Perron vector) can be used to assign positive weights to the vertices. A natural way to measure the homogeneousness of this vector is by considering the ratio of its $\ell^1$ and $\ell^2$ norms. It is easy to see that the most balanced graphs in this sense (i.e., the ones with the largest ratio) are the regular graphs. What can we say about the least balanced (or most centralized) graphs with the smallest ratio? It was conjectured by Rücker, Rücker and Gutman that, for any given $n \geq 6$, among $n$-vertex connected graphs the smallest ratio is achieved by the complete graph $K_4$ with a single path $P_{n-4}$ attached to one of its vertices. In this paper we confirm this conjecture. We also verify the analogous conjecture for trees: for any given $n \geq 8$, among $n$-vertex trees the smallest ratio is achieved by the star graph $S_5$ with a path $P_{n-5}$ attached to its central vertex. |
| title | The least balanced graphs and trees |
| topic | Combinatorics 05C50, 15A18 |
| url | https://arxiv.org/abs/2502.13939 |