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

CREATORPéter Csikvári, Viktor Harangi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE252 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-13939

Browse the full library · About the Tower of Babel