The least balanced graphs and trees
Péter Csikvári, Viktor Harangi · 2025
Read The least balanced graphs and trees by Péter Csikvári, Viktor Harangi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-13939.txt.
Introduction
Every connected network has a Perron vector, a weighting of its points drawn from its connection matrix, and the balance of that weighting says how centralized the network is. Péter Csikvári and Viktor Harangi ask the extreme question: among all connected graphs on a fixed number of points, which is the least balanced of all? A conjecture named a candidate, a four-point clique with a long path hanging off one corner.
They prove the conjecture in a 2025 paper. They also settle the matching question for trees, where the winner is a five-point star with a path attached at its center. The results pin down the most centralized shapes a network can take under this measure.
Catalog record
| CREATOR | Péter Csikvári, Viktor Harangi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 252 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-13939