2022/10/27 by Yanan Hu, Hu, Yanan, Xingzhi Zhan +3
Computer Science · Mathematics · #05C40 #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2210.15151
openalex publication_date 2022/10/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The cycles are the only 2-connected graphs in which any two nonadjacent vertices form a vertex cut. We generalize this fact by proving that for every integer k≥ 3 there exists a unique graph G satisfying the following conditions: (1) G is k-connected; (2) the independence number of G is greater than k; (3) any independent set of cardinality k is a vertex cut of G. The edge version of this result does not hold. We also consider the problem when replacing independent sets by the periphery.