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

CREATORTài Huy Hà, Takayuki Hibi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE8 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel