2025/02/11 by Huy Tài Hà, Takayuki Hibi, Hà, Tài Huy +1
Computer Science · #05C40 #13D02 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2502.07320
openalex publication_date 2025/02/11 · openalex created_date 2025/02/13 · openalex updated_date 2026/07/31
Let G be a finite graph and κ(G) the vertex connectivity of G. A chordal graph G is called chordal^* if no vertex of G is adjacent to all other vertices of G. Using the syzygy theory in commutative algebra, it is proved that every chordal^* graph G on n vertices satisfies κ(G) ≤ (n - 1) - \lceil2√(n)-2 \rceil. Furthermore, given an integer 0 ≤ κ≤ (n - 1) - \lceil2√(n)-2 \rceil, a chordal^* graph G on n vertices satisfying κ(G) = κ is constructed.