Vertex connectivity of chordal graphs
Tài Huy Hà, Takayuki Hibi · 2025
Read Vertex connectivity of chordal graphs by Tài Huy Hà, Takayuki Hibi (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-07320.txt.
Description
Tai Huy Ha and Takayuki Hibi prove a bound in graph theory in a 2025 paper. A graph is a web of points joined by lines, and its connectivity counts how many points must be removed to break it apart. They study chordal graphs, a family where every long loop has a shortcut line across it.
The pair focus on chordal graphs where no single point touches all the others. Using tools from algebra that track how equations depend on each other, they prove such a graph can only be so strongly connected. The cap depends on the number of points in a precise formula. They then build, for every allowed value, a graph that hits exactly that level of connection. The result closes the question for this family of graphs. Both the proof and the building method are part of the contribution.
Catalog record
| CREATOR | Tài Huy Hà, Takayuki Hibi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 8 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-07320