Papers › The least balanced graphs and trees
The least balanced graphs and trees
Péter Csikvári, Viktor Harangi
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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 ℓ¹ and ℓ² 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\"ucker, R\"ucker and Gutman that, for any given n ≥6, among n-vertex connected graphs the smallest ratio is achieved by the complete graph K₄ with a single path Pₙ₋₄ 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 ≥8, among n-vertex trees the smallest ratio is achieved by the star graph S₅ with a path Pₙ₋₅ attached to its central vertex.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections